Submission #1357794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1357794		mxhrvs	A String Problem (EGOI25_stringproblem)	C++20	100 / 100	413 ms	44552 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n;
    cin>>n;
    map<ll,ll> mp;
    vector<pair<ll,ll>> v;
    map<ll,ll> con;
    map<ll,ll> pos;
    for(int i = 0; i < n; i ++){
        ll a,b;
        cin >> a >> b;
        v.push_back({a,b});
        ll xd = a + b;
        xd %= 2*n;
        con[a] = b;
        con[b] = a;
        pos[a] = i;
        pos[b] = i;
        if((a+b) % 2 != 0){
            mp[xd] ++;
        }
    }
    ll ans = 0;
    ll k = 1;
    for(auto i : mp){
        if(i.second > ans){
            ans = i.second;
            k = i.first;
        }
    }
    cout << n - ans << "\n";
    map<ll,ll> vis;
    queue<ll> q;
    for(int i = 0; i < n; i ++){
        ll xd = v[i].first + v[i].second;
        xd %= 2*n;
        if(xd != k){
            q.push(v[i].second);
            while(!q.empty()){
                ll nd = q.front();
                if(vis[nd]){
                    q.pop();
                    continue;
                }
                vis[nd] = 1;
                q.pop();
                ll point = con[nd];
                vis[point] = 1;
                ll to = (k - point);
                to %= 2*n;
                if(to < 0){
                    to += 2*n;
                }
                cout << pos[nd] << " " << nd << " " << to << "\n";
                if(vis[to]){
                    continue;
                }
                q.push(to);
            }
        }
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 16 / 16
• Subtask 3: 12 / 12
• Subtask 4: 28 / 28
• Subtask 5: 30 / 30