关灯3

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int n, k;
// 每一列以及相反列
bitset<MAXN + 5> a[MAXN + 5], aa[MAXN + 5], tempB;
bool nowCol[MAXN + 5]; // 第 j 列是否整体翻转
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            int temp;
            cin >> temp;
            if (temp)
                a[j].set(i);
            else
                aa[j].set(i);
        }
    // 钦定第 col 列不进行单点操作
    for (int col = 1; col <= n; col++)
    {
        int cnt, M; // 单点次数，行次数
        // ---- 方案 1，第 col 列不翻转 ----
        cnt = M = 0;
        // 先算算自己的反转次数
        M += a[col].count();
        for (int j = 1; j <= n; j++)
        {
            if (j == col)
                continue;
            // 其他列一共需要几次
            int now = 0; // 第 col 列操作完后，第 j 列的 1 的数量
            tempB = a[col] ^ a[j];
            now += tempB.count();
            if (now <= n - now)
                cnt += now, nowCol[j] = false;
            else
                cnt += n - now, M++, nowCol[j] = true;
        }
        if (cnt <= k)
        {
            cout << cnt + M << "\n";
            // 第 col 列变化
            for (int i = 1; i <= n; i++)
                if (a[col][i] == 1)
                    cout << i << " " << 0 << "\n";
            // 其他列变化
            for (int j = 1; j <= n; j++)
            {
                if (j == col)
                    continue;
                if (nowCol[j])
                    cout << 0 << " " << j << "\n";
                for (int i = 1; i <= n; i++)
                    if (nowCol[j] == false && (a[j][i] != a[col][i]) ||
                        nowCol[j] == true && (a[j][i] == a[col][i]))
                        cout << i << " " << j << "\n";
            }
            return 0;
        } // ---- 方案 1，第 col 列不翻转 ----
        cnt = M = 0;
        // 先算算自己的反转次数
        M++;
        M += aa[col].count();
        for (int j = 1; j <= n; j++)
        {
            if (j == col)
                continue;
            // 其他列一共需要几次
            int now = 0; // 第 col 列操作完后，第 j 列的 1 的数量
            tempB = aa[col] ^ a[j];
            now += tempB.count();
            if (now <= n - now)
                cnt += now, nowCol[j] = false;
            else
                cnt += n - now, M++, nowCol[j] = true;
        }
        if (cnt <= k)
        {
            cout << cnt + M << "\n";
            // 第 col 列变化
            cout << 0 << " " << col << "\n";
            for (int i = 1; i <= n; i++)
                if (aa[col][i] == 1)
                    cout << i << " " << 0 << "\n";
            // 其他列变化
            for (int j = 1; j <= n; j++)
            {
                if (j == col)
                    continue;
                if (nowCol[j])
                    cout << 0 << " " << j << "\n";
                for (int i = 1; i <= n; i++)
                    if (nowCol[j] == false && (a[j][i] != aa[col][i]) ||
                        nowCol[j] == true && (a[j][i] == aa[col][i]))
                        cout << i << " " << j << "\n";
            }
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}