제출 #1366383

#제출 시각아이디문제언어결과실행 시간메모리
1366383neptunnsA String Problem (EGOI25_stringproblem)C++20
14 / 100
22 ms12628 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define maxn 500005
#define mi LLONG_MIN
#define ma LLONG_MAX
#define mod 1000000007
#define pb push_back
#define S second
#define F first

void solve() {
    int n;
    cin >> n;
    int md = 2 * n, mx = 0, mad = 1;
    vector<pair<int, int>> a(n), b(n * 2);
    vector<int> cnt(2 * n, 0);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if ((x + y) % 2)
            if (mx < ++cnt[(x + y) % md]) mad = (x + y) % md;
        a[i] = {x, y};
        b[x] = {i, y};
        b[y] = {i, x};
    }
    int ans = n - cnt[mad];
    // x + y == mad  ---> y = mad - x
    struct str {
        int p, s, e;
    };
    vector<str> answ;
    vector<int> used(2 * n, 0);
    for (int i = 0; i < 2 * n; i++) {
        if (used[i]) continue;
        int cur = i;
        int x = (mad - cur + md) % md;
        while (!used[x] && b[cur].S != x) {
            answ.pb({b[cur].F, b[cur].S, x});
            used[cur] = 1;
            used[x] = 1;
            cur = b[x].S;
            x = (mad - cur + md) % md;
        }
    }
    cout << ans << "\n";
    for (auto it : answ) cout << it.p << " " << it.s << " " << it.e << "\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…