제출 #1365107

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

Main

#include <bits/stdc++.h>

using namespace std;

struct endpt {
    int hair, other;
};

int main() {
    int N;
    cin >> N;
    vector<endpt> endp(2 * N);

    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        endp[a] = {i, b};
        endp[b] = {i, a};

    }
    vector<int> countSum(2 * N, 0);
    for (int i = 0; i < 2 * N; i++) {
        if ((i + endp[i].other) % 2 == 1) countSum[(i + endp[i].other) % (2 * N)]++;
    }

    int best = max_element(countSum.begin(), countSum.end()) - countSum.begin();

    int K = N - countSum[best] / 2;

    if (best == 0) best = 1;

    vector<vector<int>> answer;

    for (int i = 0; i < 2 * N; i++) {
        if ((i + endp[i].other) % (2 * N) == best) continue;
        int cur = i;
        int curBest = (best - cur + 2 * N) % (2 * N);
        endp[endp[cur].other].hair = -1;
        while (endp[curBest].hair != -1) {
            answer.push_back({endp[cur].hair, endp[cur].other, curBest});
            // cout << endp[cur].hair << " " << endp[cur].other << " " << curBest << endl;
            endp[cur].other = curBest;
            int next = endp[curBest].other;
            endp[curBest] = {endp[cur].hair, cur};
            cur = next;
            curBest = (best - cur + 2 * N) % (2 * N);
        }
        answer.push_back({endp[cur].hair, endp[cur].other, curBest});

        // cout << endp[cur].hair << " " << endp[cur].other << " " << curBest << endl;
        endp[cur].other = curBest;
        endp[curBest] = {endp[cur].hair, cur};
    }


    cout << K << endl;

    for (int i = 0; i < K; ++i) {
        int p = answer[i][0];
        int s = answer[i][1];
        int e = answer[i][2];
        cout << p << ' ' << s << ' ' << e << endl;
    }

    return 0;
}

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