Submission #1369191

#TimeUsernameProblemLanguageResultExecution timeMemory
1369191ezzzayA String Problem (EGOI25_stringproblem)C++20
100 / 100
26 ms7716 KiB
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define int long long

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

    int n;
    cin >> n;
    int m = 2 * n;

    vector<int> id(m), ot(m), cnt(m, 0), used(n, 0);

    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        id[l] = id[r] = i;
        ot[l] = r;
        ot[r] = l;

        int s = (l + r) % m;
        if (s & 1) cnt[s]++;
    }

    pair<int,int> mx = {-1, 1}; // {count, D}
    for (int d = 1; d < m; d += 2) {
        if (cnt[d] > mx.ff) mx = {cnt[d], d};
    }

    int D = mx.ss;
    cout << n - mx.ff << '\n';

    auto tgt = [&](int x) {
        int y = (D - x) % m;
        if (y < 0) y += m;
        return y;
    };

    for (int i = 0; i < m; i++) {
        int s = id[i];
        if (used[s]) continue;

        int j = ot[i];
        if ((i + j) % m == D) {
            used[s] = 1;
            continue;
        }

        int p = i;
        while (!used[id[p]]) {
            int cur = id[p];
            int q = ot[p];
            int e = tgt(q);

            cout << cur << " " << p << " " << e << '\n';
            used[cur] = 1;
            p = e;
        }
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...