小 C 正在玩一个移球游戏，他面前有 n+1n+1 根柱子，柱子从 1∼n+11∼n+1 编号，其中11 号柱子、22 号柱子、· · ·、nn 号柱子上各有 mm 个球，它们自底向上放置在柱子上，n+1n+1号柱子上初始时没有球。这 n×mn×m 个球共有 nn 种颜色，每种颜色的球各 mm 个。
初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。
小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 xx 号柱子上的球移动到 yy 号柱子上的要求为：
1. xx 号柱子上至少有一个球；
2. yy 号柱子上至多有 m−1m−1 个球；
3. 只能将 xx 号柱子最上方的球移到 yy 号柱子的最上方。
小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 820000820000。换句话说，小 C 需要使用至多 820000 次操作完成目标。
小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。
【输入】第一行两个用空格分隔的整数 nn，mm。分别表示球的颜色数、每种颜色球的个数。
接下来 nn 行每行 mm 个用单个空格分隔的整数，第 ii 行的整数按自底向上的顺序依次给出了 ii 号柱子上的球的颜色。
【输出】本题采用自定义校验器（special judge）评测。
你的输出的第一行应该仅包含单个整数 kk，表示你的方案的操作次数。你应保证0≤k≤8200000≤k≤820000。
接下来 kk 行每行你应输出两个用单个空格分隔的正整数 xx, yy，表示这次操作将 xx 号柱子最上方的球移动到 yy 号柱子最上方。你应保证 1≤x,y≤n+11≤x,y≤n+1 且 xx≠yy。
【输入样例】2 3 1 1 2 2 1 2【输出样例】
6 1 3 2 3 2 3 3 1 3 2 3 2【提示】
【样例解释】
柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。
| 操作 | 1号柱子 | 2号柱子 | 3号柱子 |
| 初始 | 1 1 2 | 2 1 2 | |
| 1 3 | 1 1 | 2 1 2 | 2 |
| 2 3 | 1 1 | 2 1 | 2 2 |
| 2 3 | 1 1 | 2 | 2 2 1 |
| 3 1 | 1 1 1 | 2 | 2 2 |
| 3 2 | 1 1 1 | 2 2 | 2 |
| 3 2 | 1 1 1 | 2 2 2 |
【数据范围】
对于所有测试点，保证 2≤n≤502≤n≤50，2≤m≤4002≤m≤400。
【校验器】
为了方便选手测试，我们下发了checker.cpp文件，选手可以编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。
编译命令为：g++ checker.cpp −o checker。
checker 的使用方式为：checker，参数依次表示输入文件与你的输出文件。
若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小范围正确，但方案错误，则校验器会给出简要的错误信息：
1. A x，表示进行到第 x 个操作时不合法。
2. B x，表示操作执行完毕后第 x 个柱子上的球不合法。
若你的方案正确，校验器会给出OK。
作者超懒，直接上代码！
#include#include#include#include#include
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(int x){
if(x >9) writeint(x/10);
putchar((x-x/10*10)^48);
}
inline int ABS(const int &x){
return x< 0 ? -x : x;
}
const int MaxN = 55;
const int MaxM = 405;
int a[MaxN][MaxM], n, m;
int count(int x,int mid){
int s = 0; rep(i,1,m) s += (a[x][i]<= mid); return s;
}
# define TOP(x) a[x][a[x][0]]
vector< pair>ans;
# define CMD(x,y) do{ ans.push_back(make_pair(x,y));\
a[y][++ a[y][0]] = a[x][a[x][0] --]; } while(false)
int pos[MaxN]; // pos[0] is empty
inline void create(int x,int s){
rep(i,1,s) CMD(x,pos[0]);
}
inline void pourOut(int x,int y,int k){
for(; k; --k) CMD(x,y);
}
inline void moveUp(int x,int want,int helper,bool sgn=1,bool f=1){
int s = count(x,want), lost = 0;
if(!sgn) s = m-s; // >want
bool wxk = false; // if it's swapped
if((m>>1)< s && f){
wxk = 1; create(helper,m-s);
swap(helper,pos[0]); // temporary
} else create(helper,s);
for(int work=s; work; )
if((TOP(x)<= want) == sgn){
CMD(x,helper); -- work;
} else { CMD(x,pos[0]); ++ lost; }
pourOut(pos[0],x,lost); // normal balls
if(!f) return ; // keep %want% in register
pourOut(helper,x,s); // put %want% on the top
if(wxk){ // restore
swap(helper,pos[0]);
pourOut(pos[0],helper,m-s);
} else pourOut(pos[0],helper,s);
}
void solve(int l,int r){
if(l == r) return ; // already done
if(l+1 == r){ // n = 2
moveUp(pos[l],l,pos[r]);
moveUp(pos[r],l,pos[l]);
pourOut(pos[l],pos[0],count(pos[l],l));
pourOut(pos[r],pos[0],count(pos[r],l));
pourOut(pos[l],pos[r],a[pos[l]][0]);
swap(pos[0],pos[l]); return ;
}
int mid = (l+r)>>1;
for(int i=l+1; i<=r; ++i){
int s1 = count(pos[i-1],mid);
int s2 = count(pos[i],mid);
bool sgn = (s1+s2 >= m); // want
if((sgn && (m>>1)< m-s1)
|| (!sgn && (m>>1)< s1)) // fill pos[i-1]
swap(pos[i],pos[i-1]), s1 = s2;
if(!s1 || s1 == m) continue; // well...
int aid = (i == r) ? pos[l] : pos[i+1];
moveUp(pos[i],mid,aid,sgn); // extract i
moveUp(pos[i-1],mid,aid,sgn^1,false);
pourOut(pos[i],pos[i-1],m-a[pos[i-1]][0]);
pourOut(aid,pos[i],m-a[pos[i]][0]);
pourOut(pos[0],aid,a[pos[0]][0]);
}
for(int i=l,j=r; imid; --j);
swap(pos[i],pos[j]);
}
solve(l,mid), solve(mid+1,r);
}
int main(){
n = readint(), m = readint();
rep(i,1,n) rep(j,1,m)
a[i][j] = readint();
rep(i,1,n) // init
pos[i] = i, a[i][0] = m;
pos[0] = n+1; solve(1,n);
writeint(ans.size());
putchar('\n');
for(auto it : ans){
writeint(it.first);
putchar(' ');
writeint(it.second);
putchar('\n');
}
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧