Submission #1342194

#TimeUsernameProblemLanguageResultExecution timeMemory
1342194gry3125A String Problem (EGOI25_stringproblem)C++20
100 / 100
89 ms5352 KiB
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ll long long int
#define all(v) (v).begin(),(v).end()
using namespace std;

int main() {
    int n; cin >> n;
    vector<pair<int,int>> v(n); // string to pins
    vector<int> m(2*n), p(2*n), p2p(2*n); // p = pin to string, p2p = pin to pin
    vector<bool> vis(n);
    int tgt = 1; int cur = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i].fi >> v[i].se;
        int sum = v[i].fi + v[i].se;
        sum %= 2*n; m[sum]++;
        p[v[i].fi] = i; p[v[i].se] = i;
        p2p[v[i].fi] = v[i].se;
        p2p[v[i].se] = v[i].fi;
    }
    for (int i = 1; i < 2*n; i += 2) {
        if (cur < m[i]) {
            cur = m[i]; tgt = i;
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int sum = v[i].fi + v[i].se;
        sum %= 2*n;
        if (sum == tgt) {vis[i] = 1; continue;}
        cnt++; 
    }
    cout << cnt << "\n";

    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        int cur = tgt - v[i].fi; cur %= 2*n;
        if (cur < 0) cur += 2*n;
        cout << i << " " << v[i].se << " " << cur << "\n";
        while (cur != v[i].se) {
            int pn = tgt - p2p[cur]; pn %= 2*n;
            if (pn < 0) pn += 2*n;
            cout << p[cur] << " " << cur << " " << pn << "\n";
            vis[p[cur]] = 1; swap(pn, cur);
        }
    }

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