Submission #1363437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363437		liptonek	A String Problem (EGOI25_stringproblem)	C++20	100 / 100	64 ms	6068 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAX_N=100005;

struct Move
{
    int p,s,e;
};

pair<int,int> strings[MAX_N];

int pin[2*MAX_N];
int freq[2*MAX_N];
bool visited[MAX_N];

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

    int n;
    cin>>n;

    for(int i=0; i<n; i++)
    {
        int a,b;
        cin>>a>>b;

        strings[i]={a,b};
        pin[a]=i;
        pin[b]=i;

        freq[(a+b)%(2*n)]++;
    }

    int best=1;
    int xf=-1;

    for(int s=1; s<2*n; s+=2)
    {
        if(freq[s]>xf)
        {
            xf=freq[s];
            best=s;
        }
    }

    auto partner=[&](int p)
    {
        return (best-p+2*n)%(2*n);
    };

    vector<Move> moves;

    for(int i=0; i<n; i++)
    {
        if((strings[i].first+strings[i].second)%(2*n)==best)
        {
            visited[i]=true;

            continue;
        }

        if(!visited[i])
        {
            int s=i;
            int curr=strings[i].first;
            int next=strings[i].second;

            while(!visited[s])
            {
                visited[s]=true;

                int target=partner(curr);

                moves.push_back({s,next,target});

                int pnp=partner(next);
                int ns=pin[pnp];

                if(visited[ns])
                {
                    break;
                }

                s=ns;
                curr=pnp;
                next=(strings[s].first==curr) ? strings[s].second : strings[s].first;
            }
        }
    }

    cout<<moves.size()<<endl;

    for(const auto& m : moves)
    {
        cout<<m.p<<" "<<m.s<<" "<<m.e<<endl;
    }

    return 0;
}

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