제출 #1369191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369191		ezzzay	A String Problem (EGOI25_stringproblem)	C++20	100 / 100	26 ms	7716 KiB

Main

#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;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 14 / 14
• 서브태스크 2: 16 / 16
• 서브태스크 3: 12 / 12
• 서브태스크 4: 28 / 28
• 서브태스크 5: 30 / 30