Submission #1349734

#TimeUsernameProblemLanguageResultExecution timeMemory
1349734candi_ositosA String Problem (EGOI25_stringproblem)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector <pair <int, int> > p(n);
    vector <int> tp(2*n);
    for(pair <int, int> &j:p){
        cin>>j.f>>j.s;
    }
    vector <int> tm(n, n);
    for(int i=0; i<n; ++i){
        tp[p[i].f]=i;
        tp[p[i].s]=i;
    }
    for(int i=0; i<n; ++i){
        if(0==((2*n+2*n-p[i].s-1-p[i].f)%(2*n))&1){
            --tm[((2*n+2*n-p[i].s-1-p[i].f)%(2*n))/2];
        }
    }
    int mn=0;
    for(int i=0; i<n; ++i){
        if(tm[i]<tm[mn]){
            mn=i;
        }
    }
    cout<<tm[mn]<<"\n";
    for(int i=0; i<n; ++i){
        if(p[i].f==(2*n+2*n-p[i].s-1-2*mn)%(2*n)){
            continue;
        }
        int ap=p[i].f;
        while(ap!=(2*n+2*n-p[tp[ap]].s-1-2*mn)%(2*n)){
            cout<<tp[ap]<<" "<<p[tp[ap]].s<<" ";
            int np=(2*n+2*n-1-2*mn-ap)%(2*n);
            p[tp[ap]].s=np;
            cout<<np<<"\n";
            if(p[tp[np]].f==np){
                int aux=p[tp[np]].f;
                p[tp[np]].f=p[tp[np]].s;
                p[tp[np]].s=aux;
            }
            np=p[tp[np]].f;
            tp[(2*n+2*n-1-2*mn-ap)%(2*n)]=tp[ap];
            ap=np;
        }
    }
    return;
}
signed main(){
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    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...