Hypyt

#include <algorithm>
#include <iostream>
#include <limits>
#include <random>
#include <set>
#include <tuple>
#include <map>
#include <vector>

using namespace std;

using P = pair<int, int>;

P operator-(P a, P b) {
    return {a.first - b.first, a.second - b.second};
}
P operator+(P a, P b) {
    return {a.first + b.first, a.second + b.second};
}

vector<P> ratko(int n, int m) {
    int nm = n * m;

    vector<P> jarj;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            jarj.push_back({i, j});
        }
    }

    mt19937 rng(1234);

    shuffle(jarj.begin() + 1, jarj.end(), rng);

    map<P, P> yksiot;
    map<P, set<P>> monikot;

    const auto lisaa = [&](int i) {
        if(i >= nm - 1) {
            throw 5;
        }
        P hyppy = jarj[i + 1] - jarj[i];
        if(monikot.count(hyppy)) {
            monikot[hyppy].insert(jarj[i]);
        } else if(yksiot.count(hyppy)) {
            monikot[hyppy].insert(yksiot[hyppy]);
            monikot[hyppy].insert(jarj[i]);
            yksiot.erase(hyppy);
        } else {
            yksiot[hyppy] = jarj[i];
        }
    };
    const auto poista = [&](int i) {
        if(i >= nm - 1) {
            throw 5;
        }
        P hyppy = jarj[i + 1] - jarj[i];
        if(yksiot.count(hyppy)) {
            yksiot.erase(hyppy);
        } else if(monikot.count(hyppy)) {
            auto& l = monikot[hyppy];
            l.erase(jarj[i]);
            if(l.size() == 1) {
                yksiot[hyppy] = *l.begin();
                monikot.erase(hyppy);
            }
        } else {
            throw 5;
        }
    };

    for(int i = 1; i < nm; ++i) {
        lisaa(i - 1);
    }

    while(!monikot.empty()) {
        vector<pair<P, P>> monikkohypyt;
        for(auto& item : monikot) {
            for(auto& x : item.second) {
                monikkohypyt.push_back({item.first, x});
            }
        }
        auto [hyppy, pos1] = monikkohypyt[uniform_int_distribution<int>(0, (int)monikkohypyt.size() - 1)(rng)];

        int i1 = 0;
        while(jarj[i1] != pos1) {
            ++i1;
            if(i1 >= nm - 1) {
                throw 5;
            }
        }

        int i2 = i1;
        while(i1 == i2) {
            i2 = uniform_int_distribution<int>(0, nm - 1)(rng);
        }

        if(i1 > i2) {
            swap(i1, i2);
        }

        if(i1 < 0 || i2 < 0 || i1 > nm - 2 || i2 > nm - 1 || i1 == i2) {
            throw 5;
        }

        poista(i1);
        if(i2 != nm - 1) {
            poista(i2);
        }

        vector<P> tmp1(i2 - i1);
        vector<P> tmp2(nm - i2 - 1);
        copy(jarj.begin() + i1 + 1, jarj.begin() + i2 + 1, tmp1.begin());
        copy(jarj.begin() + i2 + 1, jarj.end(), tmp2.begin());
        copy(tmp2.begin(), tmp2.end(), jarj.begin() + i1 + 1);
        copy(tmp1.begin(), tmp1.end(), jarj.begin() + i1 + 1 + tmp2.size());

        lisaa(i1);
        if(i2 != nm - 1) {
            lisaa(i1 + tmp2.size());
        }
    }

    return jarj;
}

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

    // ratko(50, 50);
    // return 0;
    // for(int n = 1; n <= 50; ++n) {
    //     for(int m = 1; m <= 50; ++m) {
    //         ratko(n, m);
    //     }
    // }
    // return 0;

    int tc;
    cin >> tc;

    for(int ti = 0; ti < tc; ++ti) {
        int n, m;
        cin >> n >> m;
        vector<P> jarj = ratko(n, m);
        for(int i = 1; i < (int)jarj.size(); ++i) {
            P hyppy = jarj[i] - jarj[i - 1];
            cout << hyppy.first << " " << hyppy.second << "\n";
        }
    }

    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 2

Verdict: TIME LIMIT EXCEEDED