记录编号	597622	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2020]移球游戏	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.794 s
提交时间	2024-12-06 19:25:17	内存使用	5.99 MiB

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int MAXM = 405;
const int MAXO = 820005;

int read() {
    int x = 0;
    char c = getchar(), sign = '+';
    while (c < '0' || c > '9') {
        sign = c;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return sign == '-' ? -x : x;
}

void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x < 10) putchar(x + '0');
    else {
        write(x / 10);
        putchar(x % 10 + '0');
    }
}

void output(int x = -1, char c = '\n') {
    write(x);
    putchar(c);
}

int L[MAXO], R[MAXO], move_count = 0, n, m;
int ball[MAXN][MAXM], ball_count[MAXN], tot[MAXN], pos[MAXN];

void moveBall(int x, int y) {
    ++move_count;
    L[move_count] = x;
    R[move_count] = y;
    ball[y][++ball_count[y]] = ball[x][ball_count[x]--];
}

int countColor(int x, int color) {
    int result = 0;
    for (int i = 1; i <= m; ++i)
        result += ball[x][i] == color;
    return result;
}

inline int topBall(int x) {
    return ball[x][ball_count[x]];
}

int main() {
	freopen("2020ball.in","r",stdin);
	freopen("2020ball.out","w",stdout);
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i) {
        ball_count[i] = m;
        for (int j = 1; j <= m; ++j)
            ball[i][j] = read();
    }
    ball_count[n + 1] = 0;
    for (int i = 1; i <= n + 1; ++i)
        pos[i] = i;

    // Move balls and construct zero column (from right to left)
    for (int now = n; now >= 3; --now) {
        int tmp = countColor(pos[1], now);
        for (int i = 1; i <= tmp; ++i)
            moveBall(pos[now], pos[now + 1]);

        for (int i = 1; i <= m; ++i)
            if (topBall(pos[1]) == now) moveBall(pos[1], pos[now]);
            else moveBall(pos[1], pos[now + 1]);

        for (int i = 1; i <= m - tmp; ++i)
            moveBall(pos[now + 1], pos[1]);

        for (int i = 1; i <= m; ++i)
            if (topBall(pos[2]) == now || ball_count[pos[1]] == m)
                moveBall(pos[2], pos[now + 1]);
            else
                moveBall(pos[2], pos[1]);

        swap(pos[1], pos[now]);
        swap(pos[2], pos[now + 1]);

        for (int k = 1; k < now; ++k) {
            tmp = countColor(pos[k], now);
            for (int i = 1; i <= tmp; ++i)
                moveBall(pos[now], pos[now + 1]);

            for (int i = 1; i <= m; ++i)
                if (topBall(pos[k]) == now) moveBall(pos[k], pos[now]);
                else moveBall(pos[k], pos[now + 1]);

            swap(pos[k], pos[now + 1]);
            swap(pos[k], pos[now]);
        }

        for (int i = 1; i < now; ++i)
            while (topBall(pos[i]) == now) moveBall(pos[i], pos[now + 1]);

        for (int i = 1; i < now; ++i)
            while (ball_count[pos[i]] < m) moveBall(pos[now], pos[i]);
    }

    // Construct all 1 column
    int tmp = countColor(pos[1], 1);
    for (int i = 1; i <= tmp; ++i)
        moveBall(pos[2], pos[3]);

    for (int i = 1; i <= m; ++i)
        if (topBall(pos[1]) == 1) moveBall(pos[1], pos[2]);
        else moveBall(pos[1], pos[3]);

    for (int i = 1; i <= tmp; ++i)
        moveBall(pos[2], pos[1]);

    for (int i = 1; i <= m - tmp; ++i)
        moveBall(pos[3], pos[1]);

    while (ball_count[pos[3]])
        moveBall(pos[3], pos[2]);

    for (int i = 1; i <= m - tmp; ++i)
        moveBall(pos[1], pos[3]);

    for (int i = 1; i <= m; ++i)
        if (topBall(pos[2]) == 1) moveBall(pos[2], pos[1]);
        else moveBall(pos[2], pos[3]);

    // Output the result
    output(move_count);
    for (int i = 1; i <= move_count; ++i) {
        output(L[i], ' ');
        output(R[i]);
    }

    return 0;
}