oj.uz

Submission #591493

# Submission time Handle Problem Language Result Execution time Memory
591493 2022-07-07T14:02:42 Z mosiashvililuka Sorting (IOI15_sorting) C++14
54 / 100
 67 ms 640 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[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;
        for(ii=OP; ii<I; ii++){
            P[ii]=Q[ii]=1;
        }
        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
8.0 / 8.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 0 ms 340 KB Output is correct
5 Correct 1 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 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 0 ms 340 KB Output is correct
5 Correct 1 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 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 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 1 ms 312 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.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 0 ms 340 KB Output is correct
5 Correct 1 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 1 ms 316 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 7 ms 596 KB Output is correct
23 Correct 6 ms 596 KB Output is correct
24 Correct 5 ms 580 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 4 ms 596 KB Output is correct
27 Correct 7 ms 640 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 524 KB Output is correct
2 Correct 62 ms 552 KB Output is correct
3 Correct 67 ms 528 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 524 KB Output is correct
2 Correct 62 ms 552 KB Output is correct
3 Correct 67 ms 528 KB Output is correct
4 Incorrect 1 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -