oj.uz

Submission #591584

# Submission time Handle Problem Language Result Execution time Memory
591584 2022-07-07T15:58:58 Z mosiashvililuka Sorting (IOI15_sorting) C++14
100 / 100
 351 ms 31768 KB 
#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[600009],X[600009],Y[600009],g[600009],OP,OPE,Ag[600009],x[600009],Ax[600009],PASI,lef,rig,mid,PP[600009],QQ[600009];
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;
        }
        for(i=OP; i<I; i++){
            P[i]=Q[i]=1;
        }
        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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 2 ms 724 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 2 ms 724 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 252 ms 21412 KB Output is correct
16 Correct 265 ms 29432 KB Output is correct
17 Correct 318 ms 30656 KB Output is correct
18 Correct 117 ms 27376 KB Output is correct
19 Correct 226 ms 29780 KB Output is correct
20 Correct 230 ms 30376 KB Output is correct
21 Correct 238 ms 30328 KB Output is correct
22 Correct 242 ms 26828 KB Output is correct
23 Correct 281 ms 31452 KB Output is correct
24 Correct 351 ms 31048 KB Output is correct
25 Correct 316 ms 30800 KB Output is correct
26 Correct 220 ms 30336 KB Output is correct
27 Correct 215 ms 29800 KB Output is correct
28 Correct 308 ms 30972 KB Output is correct
29 Correct 309 ms 30532 KB Output is correct
30 Correct 156 ms 29504 KB Output is correct
31 Correct 313 ms 31092 KB Output is correct
32 Correct 259 ms 30644 KB Output is correct
33 Correct 336 ms 31024 KB Output is correct
34 Correct 293 ms 31092 KB Output is correct
35 Correct 228 ms 29540 KB Output is correct
36 Correct 78 ms 28980 KB Output is correct
37 Correct 338 ms 31768 KB Output is correct
38 Correct 332 ms 30772 KB Output is correct
39 Correct 332 ms 31076 KB Output is correct