제출 #591512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591512		mosiashvililuka	정렬하기 (IOI15_sorting)	C++14	20 / 100	2 ms	468 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,lef,rig,mid,PP[200009],QQ[200009];
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++){
    lef=-1;rig=M+1;int I=0;
    while(1){
        if(lef+1>=rig) break;
        mid=(lef+rig)/2;
        I=mid;


        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){
            lef=mid;
            continue;
        }
        rig=mid;PASI=I;
        for(i=0; i<I; i++){
            PP[i]=P[i];QQ[i]=Q[i];
        }




        //PASI=I;break;



    }

    /*cout<<PASI<<"\n";
    for(i=0; i<PASI; i++){
        cout<<P[i]<<" "<<Q[i]<<"\n";
    }*/
    for(i=0; i<M; i++){
        P[i]=Q[i]=0;
    }
    for(i=0; i<PASI; i++){
        P[i]=PP[i]-1;Q[i]=QQ[i]-1;
    }
    return PASI;
}

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