Submission #1365737

#TimeUsernameProblemLanguageResultExecution timeMemory
1365737hsuan._.0528A String Problem (EGOI25_stringproblem)C++20
100 / 100
31 ms4856 KiB
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pii pair<int, int>
#define F first
#define S second
const int maxn = 5e5+10;
const int mod = 998244353;
const LL inf = 1e9;

int n, ma=-1, masum=1;
pii s[maxn];
int cnt[maxn];

int id[maxn];
int pos[maxn];
bool vis[maxn];


signed main() {
    ios_base::sync_with_stdio(0);  cin.tie(0);

    cin>>n;
    for(int i=0; i<n; i++){
        int a, b;  cin>>a>>b;
        pos[a]=b;
        pos[b]=a;
        id[a]=id[b]=i;
        cnt[(a+b)%(2*n)]++;
    }
    for(int i=0; i<2*n; i++){
        if(i%2 and ma < cnt[i])
            ma = max(ma, cnt[i]), masum=i;
    }
    cout<<n-ma<<"\n";
  
    for(int i=0; i<2*n; i++){
        if((i+pos[i])%(2*n) == masum)  continue;
        int now=i;
        while(!vis[now]){
            int m = (2*n+masum-now)%(2*n);
            int a=now, b=pos[now], c=m, d=pos[m];
            cout<<id[a]<<" "<<b<<" "<<c<<"\n";
            vis[a]=1;
            vis[b]=1;
            now=d;
        }
    }
    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...