Submission #1349798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1349798		adriines06	A String Problem (EGOI25_stringproblem)	C++20	50 / 100	163 ms	15216 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int n; cin>>n;
    vector<pair<int,int>>v(n);
    map<int,int>mp,pos;
    for(int i=0;i<n;i++){
        int a,b; cin>>a>>b;
        v[i]={a,b};
        int x=(a+b)%(2*n);
        if(x%2!=0) mp[x]++;
        pos[a]=i;
        pos[b]=i;
    }
    int maxi=0,s;
    for(auto x: mp){
        maxi=max(maxi,x.second);
        if(maxi==x.second) s=x.first;
    }
    cout<<n-maxi<<"\n";
    if(maxi==0) s=2*n-1;
    vector<int>c(n,0);
    for(int i=0;i<n;i++){
        int a=v[i].first, b=v[i].second;
        if((a+b)%(2*n)==s) c[i]=1;
    }
    for(int i=0;i<n;i++){
        int a=v[i].first, b=v[i].second;
        if((a+b)%(2*n)!=s){
            int nb=(s-a+2*n)%(2*n);
            if(c[pos[nb]]==0){
                cout<<i<<" "<<b<<" "<<nb<<"\n";
                v[i]={a,nb};
                pos[nb]=i;
                pos[b]=-1;
            }
            else{
                int na=(s-b+2*n)%(2*n);
                cout<<i<<" "<<a<<" "<<na<<"\n";
                v[i]={na,b};
                pos[na]=i;
                pos[a]=-1;
            }
        }
    }


}
int main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 7 / 14
• Subtask 2: 8 / 16
• Subtask 3: 6 / 12
• Subtask 4: 14 / 28
• Subtask 5: 15 / 30