제출 #1349743

#제출 시각아이디문제언어결과실행 시간메모리
1349743candi_ositosA String Problem (EGOI25_stringproblem)C++20
100 / 100
46 ms6100 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(((p[i].s^p[i].f)&1)==1){
            --tm[((p[i].s+1+p[i].f+4*n)%(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].s==(4*n-p[i].f+2*mn-1)%(2*n)){
            continue;
        }
        int ap=p[i].f;
        while(ap!=(4*n-p[tp[ap]].s-1+2*mn)%(2*n)){
            cout<<tp[ap]<<" "<<p[tp[ap]].s<<" ";
            int np=(4*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[(4*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...