Submission #591529

#	Time	Username	Problem	Language	Result	Execution time	Memory
591529		mosiashvililuka	Sorting (IOI15_sorting)	C++14	0 / 100	91 ms	484 KiB

sorting

#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,M,f[200009],X[200009],Y[200009],g[200009],OP,OPE,Ag[200009],x[200009],Ax[200009],PASI;
int findSwapPairs(int NN, int SS[], int MM, int XX[], int YY[], int P[], int Q[]) {
    a=NN;M=MM;
    for(i=1; i<=a; i++){
        SS[i-1]++;
    }
    for(i=1; i<=M; i++){
        X[i]=XX[i-1]+1;Y[i]=YY[i-1]+1;
    }
    for(i=1; i<=a; i++){
        f[i]=SS[i-1];
    }
 
    for(int I=1; I<=M; I++){
        for(i=1; i<=a; i++){
            g[i]=f[i];x[i]=f[i];
        }
        for(i=1; i<=I; i++){
            swap(g[X[i]],g[Y[i]]);
        }
        for(i=1; i<=a; i++){
            Ag[g[i]]=i;
            Ax[x[i]]=i;
        }
        /*if(I==3){
            for(i=1; i<=a; i++){
                cout<<g[i]<<" G ";
            }
            cout<<"\n";
        }*/
        OP=0;OPE=0;
 
        for(i=1; i<=a; i++){
            int qw=0,we=0;
            //
            if(Ag[i]!=i){
 
 
            ii=X[OP+1];jj=Y[OP+1];
            qw=x[ii];we=x[jj];
            Ax[qw]=jj;Ax[we]=ii;
            swap(x[ii],x[jj]);
 
            /*c=Ag[c];d=Ag[d];
            qw=g[c];we=g[d];
            Ag[qw]=d;Ag[we]=c;
            swap(g[c],g[d]);*/
            }
            //
 
            c=Ag[i];d=i;
            if(c==d) continue;
            if(OP>=I){
                OPE=1;
                break;
            }
 
            OP++;
            ii=Ax[g[c]];jj=Ax[g[d]];
            P[OP-1]=ii;Q[OP-1]=jj;
            /*cout<<"g[i] "<<i<<"\n";
            cout<<c<<" "<<d<<"    "<<g[c]<<" "<<g[d]<<"\n";
            cout<<Ax[g[c]]<<" "<<Ax[g[d]]<<"  "<<ii<<" "<<jj<<"\n";
            for(int ja=1; ja<=a; ja++){
                cout<<x[ja]<<" X ";
            }
            cout<<"\n";
            cout<<OP-1<<" OP "<<ii<<" "<<jj<<"\n";*/
            qw=x[ii];we=x[jj];
            /*cout<<Ag[1]<<"\n";
            for(int ja=1; ja<=a; ja++){
                cout<<x[ja]<<" X ";
            }
            cout<<"\n\n\n";
            for(int ja=1; ja<=a; ja++){
                cout<<Ax[ja]<<" X ";
            }
            cout<<"\n\n\n";
            cout<<ii<<" "<<jj<<"\n";
            exit(0);*/
            Ax[qw]=jj;Ax[we]=ii;
            swap(x[ii],x[jj]);
 
            qw=g[c];we=g[d];
            Ag[qw]=d;Ag[we]=c;
            swap(g[c],g[d]);
        }
        if(OPE==1) continue;
        PASI=I;break;
    }
 
    /*cout<<PASI<<"\n";
    for(i=0; i<PASI; i++){
        cout<<P[i]<<" "<<Q[i]<<"\n";
    }*/
    for(i=0; i<PASI; i++){
        P[i]--;Q[i]--;
    }
    return PASI;
}

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