Submission #1192795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192795		simona1230	Sorting (IOI15_sorting)	C++20	100 / 100	101 ms	16400 KiB

sorting

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

//static FILE *_inputFile, *_outputFile;

int n;
vector<pair<int,int> > v;
int p[200001],pos[200001];
void swaps()
{
    //for(int i=0;i<n;i++)
    //    fprintf(_outputFile,"%d ",p[i]);
    //    fprintf(_outputFile,"\n");
    for(int i=0; i<n; i++)
        pos[p[i]]=i;
    for(int i=0; i<n; i++)
    {
        if(p[i]!=i)
        {
            v.push_back({i,p[i]});
            //fprintf(_outputFile, "%d %d\n", i,p[i]);
            pos[p[i]]=pos[i];
            swap(p[i],p[pos[i]]);
            pos[i]=pos[p[i]];
        }
    }
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[],int P[],int Q[])
{
    n=N;
    int ans=0;
    int l=0,r=M;
    while(l<=r)
    {
        int m=(l+r)/2;
        for(int i=0; i<n; i++)
            p[i]=S[i];
        for(int i=0; i<m; i++)
            swap(p[X[i]],p[Y[i]]);
        v.clear();
        swaps();
        if(v.size()<=m)
        {
            r=m-1;
            ans=m;
        }
        else l=m+1;
    }

    for(int i=0; i<n; i++)
        p[i]=S[i];
    for(int i=0; i<ans; i++)
        swap(p[X[i]],p[Y[i]]);
    v.clear();
    swaps();
    //for(int i=0;i<v.size();i++)
    //    fprintf(_outputFile, "%d %d ", v[i].first, v[i].second);

    for(int i=0;i<M;i++)
        P[i]=Q[i]=0;
    for(int i=0;i<n;i++)
        p[i]=S[i];
    for(int i=0; i<n; i++)
        pos[p[i]]=i;

    for(int i=0; i<ans; i++)
    {
        pos[p[Y[i]]]=X[i];
        pos[p[X[i]]]=Y[i];
        swap(p[X[i]],p[Y[i]]);

        if(i<v.size())
        {
            P[i]=pos[v[i].first];
            Q[i]=pos[v[i].second];
        }
        if(P[i]>Q[i])swap(P[i],Q[i]);
        pos[p[P[i]]]=Q[i];
        pos[p[Q[i]]]=P[i];
        swap(p[P[i]],p[Q[i]]);
    }
    return ans;
}

/*int nn,mm;
int ss[200001];
int xx[200001],yy[200001];
int pp[200001],qq[200001];
int gg[200001];
int main()
{
    while(1)
    {
        nn=6;
        mm=3;
        for(int i=0;i<nn;i++)
            ss[i]=i;
        for(int i=0;i<mm;i++)
        {
            int x,y;
            x=rand()%6;
            y=rand()%6;
            //cin>>x>>y;
            //cin>>xx[i]>>yy[i];
            swap(ss[x],ss[y]);
            xx[mm-i-1]=rand()%6;
            yy[mm-i-1]=rand()%6;
            swap(ss[xx[i]],ss[yy[i]]);
        }
        for(int i=0;i<nn;i++)
            gg[i]=ss[i];
        int ans=findSwapPairs(nn,ss,mm,xx,yy,pp,qq);


        //cout<<ans<<endl;
        for(int i=0;i<ans;i++)
        {
            swap(ss[xx[i]],ss[yy[i]]);
            //cout<<pp[i]<<" "<<qq[i]<<endl;
            swap(ss[pp[i]],ss[qq[i]]);
        }
        for(int i=0;i<nn;i++)
        {
            if(ss[i]!=i)
            {
                cout<<nn<<endl;
                for(int j=0;j<nn;j++)
                    cout<<gg[j]<<" ";
                cout<<endl;
                for(int j=0;j<mm;j++)
                    cout<<xx[j]<<" "<<yy[j]<<endl;
                return 0;
            }
        }
    }
}
*/

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26