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

void tc() {
    int n; cin >> n;
    int cnt = 0;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        cnt += a[i];
    }
    if(cnt >= n - cnt) {
        cout << "Bessie\n";
    } else {
        cout << "Elsie\n";
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

#include<bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, k; cin >> n >> k;
    int x = k-n+1;
    if(!(1 <= x && x <= n)) { cout << -1; return; }
    vector<vector<int>> ans(n, vector<int>(n));
    ans[0][0] = 1;
    int on = 2;
    for(int i = 1; i < x; i++) {
        ans[0][i] = on; on++;
        ans[i][0] = on; on++;
    }
    for(int i = x; i < n; i++) {
        ans[i][i] = on; on++;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(!ans[i][j]) {
                ans[i][j] = on; on++;
            }
        }
    }

    for(int j = 0; j < n; j++) {
        if(j) cout << "\n";
        for(auto &i : ans[j]) cout << i << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        solve();
        if(t)   cout << "\n";
    }
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

void tc() {
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    vector<pair<int, int>> goodivs;
    vector<pair<int, int>> badivs;
    for(int i = 1; i <= n; i++) {
        badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
        for(int j = 0; j < b[i]; j++) {
            goodivs.push_back({j * i, (j + 1) * i - 1});
        }
    }
    vector<int> d(n + 1);
    for(auto [l, r] : badivs) {
        d[min(n, l)]++;
        d[min(n, r + 1)]--;
    }
    int csm = 0;
    vector<int> gnums;
    for(int i = 0; i < n; i++) {
        csm += d[i];
        if(csm == 0) {
            gnums.push_back(i);
        }
    }
    cout << gnums.size() << endl;
    for(int i : gnums) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

const int MOD = 1e9 + 7;

void tc() {
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    vector<pair<int, int>> goodivs;
    vector<pair<int, int>> badivs;
    for(int i = 1; i <= n; i++) {
        if(b[i] > (n - 1) / i + 1) {
            cout << 0 << endl;
            return;
        }
        badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
        for(int j = 0; j < b[i]; j++) {
            goodivs.push_back({j * i, (j + 1) * i - 1});
        }
    }
    vector<int> d(n + 1);
    for(auto [l, r] : badivs) {
        d[min(n, l)]++;
        d[min(n, r + 1)]--;
    }
    int csm = 0;
    vector<int> gnums;
    for(int i = 0; i < n; i++) {
        csm += d[i];
        if(csm == 0) {
            gnums.push_back(i);
        }
    }
    set<pair<int, int>> st;
    sort(goodivs.begin(), goodivs.end(), [&] (pair<int, int> iv, pair<int, int> iv2) {
        return iv.second - iv.first < iv2.second - iv2.first;
    });
    for(auto [l, r] : goodivs) {
        auto it = st.lower_bound({l, 0});
        if(it != st.end() && it->second <= r) {
            continue;
        }
        st.insert({l, r});
    }

    vector<pair<int, int>> impivs(st.begin(), st.end());
    int l = 0, r = 0;
    vector<int> dp(impivs.size() + 1);
    dp[0] = 1;
    int poss = 1;
    for(int i : gnums) {
        while(l < impivs.size() && impivs[l].second < i) {
            poss += MOD - dp[l];
            poss %= MOD;
            l++;
        }
        while(r < impivs.size() && impivs[r].first <= i) r++;
        dp[r] += poss;
        dp[r] %= MOD;
        poss += poss;
        poss %= MOD;
    }
    cout << dp[impivs.size()] << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

using ll = long long;

struct BIT {
    vector<ll> tr;
    BIT(int n) : tr(n + 1) {}
    void add(int k, ll x) {
        while(k < tr.size()) {
            tr[k] += x;
            k += k&-k;
        }
    }
    ll sum(int k) {
        ll res = 0;
        while(k > 0) {
            res += tr[k];
            k -= k&-k;
        }
        return res;
    }
};

void tc() {
    int n; cin >> n;
    vector<int> a(n), p(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> p[i]; p[i]--;
    }
    reverse(p.begin(), p.end());
    BIT bit(n);
    set<int> imp; 
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        int k = p[i];
        auto it = imp.upper_bound(k);
        int pimp;
        if(it == imp.begin() || bit.sum(k) - bit.sum(*prev(it)) < a[k]) {
            imp.insert(k);
            pimp = k;
        } else {
            pimp = *prev(it);
        }
        bit.add(k + 1, a[k]);
        while(imp.upper_bound(k) != imp.end()) {
            int j = *imp.upper_bound(k);
            if(bit.sum(j) - bit.sum(pimp) >= a[j]) {
                imp.erase(j);
            } else {
                break;
            }
        }
        ans[i] = imp.size() - 1;
    }
    reverse(ans.begin(), ans.end());
    for(int i : ans) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

using ll = long long;

const int MOD = 1e9 + 7;

void tc() {
    int n; cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int k = n / 2;

    int val = 1;
    for(int i = 1; i <= k; i++) {
        val = (ll)i * val % MOD;
    }
    for(int i = 1; i <= k - (n % 2 == 0 ? 2 : 1); i++) {
        val = (ll)i * val % MOD;
    }

    set<ll> xposs;
    xposs.insert(a[n - 1] - a[n - 2]);
    xposs.insert(a[n - 1] - a[n - 3]);

    int ans = 0;
    for(ll x : xposs) {
        vector<ll> b;
        for(int i = 0; i < k; i++) {
            b.push_back(i * x);
        }
        for(int i = 0; i < n - k; i++) {
            b.push_back(a[n - 1] - i * x);
        }
        sort(b.begin(), b.end());
        if(a == b) {
            ans += val;
            if(ans >= MOD) ans -= MOD;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

void tc() {
    int n; cin >> n;

    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i], a[i]--;
    for(int i = 0; i < n; i++) cin >> b[i], b[i]--;

    int badcnt = 0;
    for(int i = 0; i < n; i++) {
        badcnt += a[i] != b[i];
    }
    if(badcnt == 0) {
        cout << "0 1\n";
        return;
    }

    // mark everything which will ever be reached
    vector<bool> useful(n);
    for(int i = 0; i < n; i++) {
        if(a[i] == b[i]) continue;
        int x = i;
        while(!useful[x]) {
            useful[x] = true;
            x = b[x];
        }
    }

    // anything with b[i] == i once we reach we can't reach anything else, 
    // at most one of them can exit
    vector<int> ends;
    for(int i = 0; i < n; i++) {
        if(useful[i] && b[i] == i) ends.push_back(i);
    }

    if(ends.size() > 1) {
        cout << "-1\n";
        return;
    }

    vector<vector<int>> adj(n), radj(n);
    for(int i = 0; i < n; i++) {
        if(a[i] > b[i]) {
            cout << "-1\n";
            return;
        }
        for(int j = a[i]; j <= b[i]; j++) {
            adj[i].push_back(j);
            radj[j].push_back(i);
        }
    }

    // tarjan algorithm, from cp-algorithms
    vector<int> st;    // - stack holding the unclaimed vertices
    vector<int> roots(n, -1); // - keeps track of the SCC roots of the vertices
    int timer = 0;         // - dfs timestamp counter
    vector<int> t_in(n, -1);  // - keeps track of the dfs timestamp of the vertices
    vector<int> t_low(n, -1); // - keeps track of the lowest t_in of unclaimed vertices
    // reachable in the subtree

    // implements the tarjan algorithm for strongly connected components
    auto dfs = [&](auto&& self, int s) -> void {
        t_low[s] = t_in[s] = timer++;
        st.push_back(s);

        for (auto u : adj[s]) {
            if (t_in[u] == -1) { // tree-edge
                self(self, u);
                t_low[s] = min(t_low[s], t_low[u]);
            } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
                t_low[s] = min(t_low[s], t_in[u]);
            }
        }

        if (t_low[s] == t_in[s]) { // vertex is a root
            while (true) {
                int u = st.back();
                st.pop_back();
                roots[u] = s; // claims the vertex
                if (u == s)
                    break;
            }
        }
    };

    // applies the tarjan algorithm to all the vertices
    for (int v = 0; v < n; v++) {
        if (t_in[v] == -1) {
            dfs(dfs, v);
        }
    }
    vector<vector<int>> comps(n);
    for(int v = 0; v < n; v++) {
        comps[roots[v]].push_back(v);
    }

    vector<int> p(n, -1);
    vector<int> sz(n);
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) {
            sz[roots[i]]++;
        }
        if(useful[i] && roots[i] != roots[b[i]]) {
            if(p[roots[b[i]]] != -1) {
                cout << "-1\n";
                return;
            }
            p[roots[b[i]]] = roots[i];
        }
    }
    vector<int> chain;
    int x = roots[ends[0]];
    int csz = 0;
    while(x != -1) {
        chain.push_back(x);
        csz += sz[x];
        x = p[x];
    }
    if(csz != badcnt) {
        cout << "-1\n";
        return;
    }
    reverse(chain.begin(), chain.end());

    {
        x = comps[chain[0]][0];
        vector<int> ops;
        auto op1 = [&] () {
            ops.push_back(1);
            a[x]++;
        };
        auto op2 = [&] () {
            ops.push_back(2);
            x = a[x];
        };
        auto solve_scc = [&] () {
            int rt = roots[x];
            vector<int> comp = comps[rt];

            vector<int> p2(n, -1);
            // only one thing in comp case
            auto rdfs = [&] (auto&& self, int s) -> void {
                for(int u : radj[s]) {
                    if(roots[u] != rt) continue;
                    if(p2[u] == -1) {
                        p2[u] = s;
                        self(self, u);
                    }
                }
            };

            // root a tree
            rdfs(rdfs, comp[0]);

            for(int i = 0; i < comp.size(); i++) {
                while(x != comp[i]) {
                    while(a[x] < max(p2[x], comp[i])) op1();
                    op2();
                }
                while(a[x] < b[x]) op1();
                op2();
            }
        };
        for(int i = 0; i < chain.size(); i++) solve_scc();

        cout << ops.size() << " " << comps[chain[0]][0] + 1 << endl;
        for(int i : ops) cout << i << " ";
        cout << endl;

        for(int i = 0; i < n; i++) assert(a[i] == b[i]);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

With this, you can prove a significantly simpler solution. We will add this proof later.

// Note: AI generated solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n + 1), b(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> b[i];
        }

        int start = 1, remaining = 0;
        bool possible = true;

        for (int i = 1; i <= n; i++) {
            if (a[i] > b[i]) {
                possible = false;
            }
            if (a[i] < b[i]) {
                if (remaining == 0) {
                    start = i;
                }
                remaining++;
            }
        }

        if (!possible) {
            cout << -1 << '\n';
            continue;
        }

        vector<int> operations;
        int position = start;

        while (remaining > 0) {
            if (a[position] < b[position]) {
                while (a[position] < b[position] &&
                       (a[position] >= position ||
                        a[a[position]] == b[a[position]])) {
                    a[position]++;
                    operations.push_back(1);
                }

                if (a[position] == b[position]) {
                    remaining--;
                }
            }

            if (remaining == 0 || a[position] == position) {
                break;
            }

            operations.push_back(2);
            position = a[position];
        }

        if (remaining > 0) {
            cout << -1 << '\n';
            continue;
        }

        cout << operations.size() << ' ' << start << '\n';
        for (int operation : operations) {
            cout << operation << ' ';
        }
        cout << '\n';
    }
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

int MOD;

void madd(int& a, int b) {
    a += b;
    if(a >= MOD) a -= MOD;
}

void msub(int& a, int b) {
    a -= b;
    if(a < 0) a += MOD;
}

int mmul(int a, int b) {
    return 1LL * a * b % MOD;
}

int bpow(int x, int y) {
    return y == 0 ? 1 : mmul((y % 2) ? x : 1, bpow(mmul(x, x), y / 2));
}

void tc() {
    int n; cin >> n >> MOD;
    vector<int> f(2 * n + 1), invf(2 * n + 1);
    f[0] = 1;
    for(int i = 1; i <= 2 * n; i++) {
        f[i] = mmul(f[i - 1], i);
    }
    invf[2 * n] = bpow(f[2 * n], MOD - 2);
    for(int i = 2 * n; i >= 1; i--) {
        invf[i - 1] = mmul(invf[i], i);
    }
    auto F = [&] (int n, int k) -> int {
        return mmul(f[n], mmul(invf[k + 1], invf[n - k]));
    };
    auto choose = [&] (int n, int k) -> int {
        return mmul(f[n], mmul(invf[k], invf[n - k]));
    };
    vector<vector<int>> p(n + 1, vector<int>(n + 1));
    for(int i = 0; i <= n; i++) {
        p[0][i] = mmul(F(2 * i, i), F(2 * i, i));
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            for(int k = 0; j + k <= n; k++) {
                madd(p[i][j + k], mmul(p[i - 1][j], p[0][k]));
            }
        }
    }
    vector<int> ans(n + 1);
    for(int i = 0; i <= n; i++) {
        ans[i] = mmul(F(2 * n, i), p[i][n - i]);
    }
    for(int i = n - 1; i >= 0; i--) {
        for(int j = i + 1; j <= n; j++) {
            msub(ans[i], mmul(ans[j], choose(j, i)));
        }
    }
    for(int i = 0; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t; 
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible:

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

const int MXN = 400;

template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {
    int n = mat.size();
    vector<bool> empty(n, true);
    vector<bitset<SZ>> basis(n);

    for(int i = 0; i < n; i++) {
        bitset<SZ> cur = mat[i];
        bitset<SZ> curinv;
        curinv[i] = 1;
        for(int j = 0; j < n; j++) {
            if(cur[j]) {
                if(empty[j]) {
                    basis[j] = cur;
                    inv[j] = curinv;
                    empty[j] = false;
                    break;
                } else {
                    cur ^= basis[j];
                    curinv ^= inv[j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(empty[i]) return 0;
    }

    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j < i; j++) {
            if(basis[j][i]) {
                basis[j] ^= basis[i];
                inv[j] ^= inv[i];
            }
        }
    }
    return 1;
}

bool try_removal(vector<pair<int, int>> cells, vector<bitset<MXN>>& mat, vector<bitset<MXN>>& inv, vector<int>& row_cnt) {
    int n = mat.size(), k = cells.size();
    for(auto [x, y] : cells) {
        if(mat[x][y] == 0) {
            return false;
        }
    }
    assert(k < 4);
    vector<bitset<3>> K(k); 
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k; j++) {
            K[i][j] = (i == j) ^ inv[cells[i].second][cells[j].first];
        }
    }
    vector<bitset<3>> invK(cells.size());
    if(!compute_inv(K, invK)) {
        return false;
    }
    for(auto [x, y] : cells) {
        mat[x][y] = 0;
        row_cnt[x]--;
    }

    auto old = inv;
    for(int i = 0; i < n; i++) {
        bitset<3> coef;
        for(int alpha = 0; alpha < k; alpha++) {
            int r = cells[alpha].first;

            if(old[i][r]) {
                coef ^= invK[alpha];
            }
        }

        // delta = coef * (V^T * old)
        for(int beta = 0; beta < k; beta++) {
            if(coef[beta]) {
                int c = cells[beta].second;
                inv[i] ^= old[c];
            }
        }
    }
    return true;
}

vector<int> compute_matching(const vector<bitset<MXN>>& mat) {
    int n = mat.size();
    vector<vector<int>> adj(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(mat[i][j]) adj[i].push_back(j);
        }
    }

    vector<int> match(n, -1);
    vector<bool> done(n);

    function<bool(int)> dfs = [&] (int s) {
        for(int u : adj[s]) {
            if(!done[u]) {
                done[u] = true;

                if(match[u] == -1 || dfs(match[u])) {
                    match[u] = s;
                    return true;
                }
            }
        }
        return false;
    };

    for(int i = 0; i < n; i++) {
        fill(done.begin(), done.end(), false);
        dfs(i);
    }

    for(int i = 0; i < n; i++) {
        assert(match[i] != -1);
    }
    return match;
}

void tc() {
    int n, m; cin >> n >> m;

    vector<bitset<MXN>> mat(n);
    vector<int> row_cnt(n);
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        mat[x][y] = 1;
        row_cnt[x]++;
    }

    vector<bitset<MXN>> inv(n);
    compute_inv(mat, inv);

    int sm = m;
    int left = (sm + n - 1) / n;
    cout << left << '\n';

    while(sm > 0) {
        vector<bitset<MXN>> omat = mat;
        if(sm <= n) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
            row_cnt.assign(n, 0);
        } else if(sm <= 2 * n) {
            vector<int> matching = compute_matching(mat);
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
            row_cnt.assign(n, 0);
            for(int i = 0; i < sm - n; i++) {
                mat[matching[i]][i] = 1;
                row_cnt[matching[i]]++;
            }
        } else if(sm <= 3 * n) {
            vector<int> matching = compute_matching(mat);
            int above = 0;
            for(int i = 0; i < n; i++) {
                for(int j = matching[i] + 1; j < n; j++) {
                    above += mat[j][i];
                }
            }

            vector<bitset<MXN>> nmat(n);
            vector<int> nrow_cnt(n);
            int ones_left = sm - n;
            for(int i = 0; i < n; i++) {
                nmat[matching[i]][i] = 1;
                nrow_cnt[matching[i]]++;
                ones_left--;
            }
            // make matrix either upper or lower triangular, whichever one
            // removes a sufficient number of ones
            if(above >= ones_left) {
                for(int i = 0; i < n; i++) {
                    for(int j = matching[i] + 1; j < n; j++) {
                        if(mat[j][i]) {
                            ones_left--;
                            nmat[j][i] = 1;
                            nrow_cnt[j]++;
                            if(ones_left == 0) break;
                        }
                    }
                    if(ones_left == 0) break;
                }
            } else {
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < matching[i]; j++) {
                        if(mat[j][i]) {
                            ones_left--;
                            nmat[j][i] = 1;
                            nrow_cnt[j]++;
                            if(ones_left == 0) break;
                        }
                    }
                    if(ones_left == 0) break;
                }
            }
            mat = nmat;
            row_cnt = nrow_cnt;
        } else {
            int csm = sm;
            if(n % 2) {
                // odd case (remove either 1 or 3)
                int dup_row = -1;
                for(int i = 0; i < n; i++) {
                    if(row_cnt[i] >= 2) {
                        dup_row = i;
                        break;
                    }
                }
                assert(dup_row != -1);

                vector<int> cols;
                for(int i = 0; i < n; i++) {
                    if(mat[dup_row][i]) cols.push_back(i);
                }

                assert(cols.size() >= 2);

                for(int i = 0; i < n; i++) {
                    if(try_removal({{i, cols[0]}}, mat, inv, row_cnt)) {
                        csm--;
                        break;
                    }
                    if(try_removal({{i, cols[1]}}, mat, inv, row_cnt)) {
                        csm--;
                        break;
                    }
                }

                if(csm == sm) {
                    for(int i = 0; i < n; i++) {
                        if(i != dup_row) {
                            // remove L shape
                            if(try_removal(
                                    {{i, cols[0]}, 
                                     {dup_row, cols[0]}, 
                                     {dup_row, cols[1]}},
                                mat, inv, row_cnt)) {
                                csm -= 3;
                                break;
                            }
                        }
                    }
                    assert(sm != csm);
                }
            }

            while(csm > sm - n) {
                // remove 2 at a time
                int dup_row = -1;
                for(int i = 0; i < n; i++) {
                    if(row_cnt[i] >= 3) {
                        dup_row = i;
                        break;
                    }
                }

                vector<int> cols;
                for(int i = 0; i < n; i++) {
                    if(mat[dup_row][i]) cols.push_back(i);
                }

                assert(cols.size() >= 3);

                if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[1]}}, mat, inv, row_cnt)) {
                    if(!try_removal({{dup_row, cols[1]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {
                        if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {
                            assert(false);
                        }
                    }
                }

                csm -= 2;
            }
            assert(csm == sm - n);
        }

        vector<pair<int, int>> move;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(omat[i][j] == 1 && mat[i][j] == 0) {
                    move.push_back({i, j});
                }
            }
        }
        cout << move.size() << "\n";
        for(auto [x, y] : move) cout << x + 1 << " " << y + 1 << "\n";
        sm -= n;

        int csm = 0;
        for(int i = 0; i < n; i++) {
            csm += row_cnt[i];
        }
        assert(csm == max(0, sm));
    }
}

int main() {
    int t; cin >> t;
    while(t--) tc();
}

Credit to BurnedChicken for finding this in testing!

We will first prove that for any row/column of a rank $$$n$$$ matrix, we can zero out everything in that row/column except one, and maintain rank $$$n$$$. This is because rank $$$n$$$ means the determinant is $$$1$$$, so there are exactly an odd number of perfect matchings in total (read Solution 1 for more understanding). Therefore at least $$$1$$$ of the ones in the row/column must be in an odd number of perfect matchings (since if they were all even then the total number would be even). This means if we delete all other ones but that one, then we would keep rank $$$n$$$.

This actually all you need to prove to solve the problem. Note that after we clear out one row except one number, we can clear out that column except that one number (even partially) and the determinant will not change (and the same works when clearing out a column with the leftover row).

For every turn, we want to try to find $$$n$$$ things to remove without changing the rank. Therefore, we begin by finding the one in the biggest row/column we can keep while removing everything else. Then we remove everything in the column/row of that one, and the everything in the row/column into the queue. If the queue + the current removals is big enough to reach $$$n$$$ removals, then we can just remove the ones in the queue. If the queue is too small, then we repeat one the next biggest row/column. Because the queue contains the row/column with the most ones, when the current removals will never exceed $$$n$$$ if the the queue + current removals is less than $$$n$$$. Once we run out of row/columns to clear, we can start removing the ones we excluded removing, since we have to reduce the rank at this point.

To find the one we must keep, you have to utilize the inverse, since we can clear out the row/column on $$$M_{i, j}$$$ if $$$M^{-1}_{j, i} = 1$$$ (proof is by Cramer's Rule). We can keep track of the inverse after this clear out operation in $$$O(n^2 / w)$$$ if done properly (using something similar to Woodbury Matrix Identity, look at Solution 1 for details). If implemented properly, this results in a $$$O(n^3 / w)$$$ solution.

#include <bits/stdc++.h>
using namespace std;
 
const int SZ = 400;
 
 
template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {
    int n = mat.size();
    vector<bool> empty(n, true);
    vector<bitset<SZ>> basis(n);
 
    for(int i = 0; i < n; i++) {
        bitset<SZ> cur = mat[i];
        bitset<SZ> curinv;
        curinv[i] = 1;
        for(int j = 0; j < n; j++) {
            if(cur[j]) {
                if(empty[j]) {
                    basis[j] = cur;
                    inv[j] = curinv;
                    empty[j] = false;
                    break;
                } else {
                    cur ^= basis[j];
                    curinv ^= inv[j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(empty[i]) return 0;
    }
 
    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j < i; j++) {
            if(basis[j][i]) {
                basis[j] ^= basis[i];
                inv[j] ^= inv[i];
            }
        }
    }
    return 1;
}
 
void tc() {
    int n, m; cin >> n >> m;
    vector<bitset<SZ>> mat(n);
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        mat[x][y] = 1;
    }
 
    vector<bitset<SZ>> inv(n);
    compute_inv(mat, inv);
    vector<int> cnts(2 * n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cnts[i] += mat[i][j];
            cnts[n + j] += mat[i][j];
        }
    }
    queue<pair<int, int>> mustq, freeq;
    vector<pair<int, int>> centers;
    vector<vector<pair<int, int>>> moves;
    while(true) {
        while(mustq.size() + freeq.size() < n) {
            int best_rc = 0;
            for(int rc = 0; rc < 2 * n; rc++) {
                if(cnts[rc] >= cnts[best_rc]) best_rc = rc;
            }
            if(cnts[best_rc] == 0) {
                break;
            }
 
            int x = -1, y = -1;
            if(best_rc < n) {
                x = best_rc;
                for(int j = 0; j < n; j++) {
                    if(mat[x][j] && inv[j][x]) {
                        y = j;
                        break;
                    }
                }
            } else {
                y = best_rc - n;
                for(int j = 0; j < n; j++) {
                    if(mat[j][y] && inv[y][j]) {
                        x = j;
                        break;
                    }
                }
            }
            assert(x != -1 && y != -1);
 
            centers.push_back({x, y});
            vector<pair<int, int>> must, free;
            auto erase = [&] (int a, int b) {
                mat[a][b] = 0;
                cnts[a]--;
                cnts[b + n]--;
            };
            for(int j = 0; j < n; j++) {
                if(mat[x][j] && j != y) {
                    must.push_back({x, j});
                    erase(x, j);
                }
            }
            for(int j = 0; j < n; j++) {
                if(mat[j][y] && j != x) {
                    free.push_back({j, y});
                    erase(j, y);
                }
            }
            erase(x, y);
            assert(cnts[x] == 0 && cnts[n + y] == 0);
 
            if(best_rc < n) swap(must, free);
            for(auto u : must) mustq.push(u);
            for(auto u : free) freeq.push(u);
 
            bitset<SZ> row = inv[y];
            for(int j = 0; j < n; j++) {
                if(cnts[j + n] > 0 && inv[j][x]) {
                    inv[j] ^= row;
                }
            }
        }
        int left = n;
        vector<pair<int, int>> move;
        while(left > 0 && mustq.size() > 0) {
            left--;
            move.push_back(mustq.front());
            mustq.pop();
        }
        while(left > 0 && freeq.size() > 0) {
            left--;
            move.push_back(freeq.front());
            freeq.pop();
        }
        while(left > 0 && centers.size() > 0) {
            left--;
            move.push_back(centers.back());
            centers.pop_back();
        }
        moves.push_back(move);
        if(centers.size() == 0) break;
    }
    cout << moves.size() << "\n";
    for(auto move : moves) {
        cout << move.size() << "\n";
        for(auto [u, v] : move) cout << u + 1 << " " << v + 1 << "\n";
    }
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

• Amazing:
• Good:
• Ok:
• Bad:
• Terrible: