http://acm.pku.edu.cn/JudgeOnline/problem?id=1033
Код:
#include <stdio.h> #include <string.h> #define MAXN 12345 class node{public: int pos,aim;}; node que[2][MAXN]; int tail[2]; int disk[MAXN]; int n,m; void readin(){ int i,j,k,l; scanf("%d%d",&n,&m); memset(disk,0,sizeof(disk)); l = 0; for (i = 0; i < m; i++) { scanf("%d",&k); for (j = 0; j < k; j++,l++) { scanf("%d",&que[0][l].pos); que[0][l].aim = l+1; disk[que[0][l].pos] = que[0][l].aim; } } tail[0] = l; } void doit(){ int flag1; int i,j,k,l,o,p,q; int count; count = 0; p = 0; do { flag1 = 0; q = p ^ 1; tail[q] = 0; for (i = 0; i < tail[p]; i++) { if (que[p][i].pos == que[p][i].aim) continue; if (disk[que[p][i].aim] == 0) { printf("%d %d\n",que[p][i].pos,que[p][i].aim); flag1 = 1; disk[que[p][i].aim] = que[p][i].aim; disk[que[p][i].pos] = 0; count++; } else { que[q][tail[q]] = que[p][i]; tail[q]++; } } p = q; q = p ^ 1; tail[q] = 0; for (i = tail[p] - 1; i >= 0; i--) { if (que[p][i].pos == que[p][i].aim) continue; if (disk[que[p][i].aim] == 0) { printf("%d %d\n",que[p][i].pos,que[p][i].aim); flag1 = 1; disk[que[p][i].aim] = que[p][i].aim; disk[que[p][i].pos] = 0; count++; } else { que[q][tail[q]] = que[p][i]; tail[q]++; } } p = q; if (flag1) continue; for (i = n; i >= 1; i--) if (disk[i] == 0) break; if (tail[p] == 0) continue; j = tail[p] / 2; printf("%d %d\n",que[p][j].pos,i); disk[que[p][j].pos] = 0; disk[i] = que[p][j].aim; que[p][j].pos = i; count++; } while (tail[p]); if (count == 0) printf("No optimization needed\n"); } int main(){ readin(); doit(); return 0; }