oj.uz

Submission #137832

# Submission time Handle Problem Language Result Execution time Memory
137832 2019-07-28T10:37:06 Z dolphingarlic Sorting (IOI15_sorting) C++14
100 / 100
 651 ms 28280 KB 
#include "sorting.h"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int inf = 6e5+9;
int n,m,x[inf],y[inf],a[inf],pos[inf],from[inf],origin[inf],posfrom[inf];
 
bool check(int i,int p[],int q[]){
 
        int l = 0,notvalid = 0;
        for(int j=0;j<n;j++){
            from[j] = j;
            a[j] = origin[j];
            p[j] = q[j] = 0;
            pos[ a[j] ] = j;
            posfrom[ from[j] ] = j;
            notvalid += (a[j] != j);
        }
        //cout<<i<<" "<<notvalid<<endl;
         for(int j=i;j>=0;j--){
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
            swap( from[ x[j] ] , from[ y[j] ] );
        }
 
        for(int j=0;j<=i;j++){
 
            swap(pos[ a[ x[j] ] ] , pos[ a[ y[j] ] ]);
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
 
            notvalid -= (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(a[ x[j] ] , a[ y[j] ] );
            notvalid += (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(from[ x[j] ] , from[ y[j] ]);
 
            //cout<<notvalid<<" ";
            int idx,idfrom;
 
            while(l<n){
                idx = pos[l];
                idfrom = posfrom[l];
                if(idx != idfrom)
                    break;
                l++;
            }
            swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
            notvalid -= (a[idx] != idx) + (a[idfrom] != idfrom);
            swap(a[idx],a[idfrom]);
            notvalid += (a[idx] != idx) + (a[idfrom] != idfrom);
 
            //cout<<notvalid<<" ";
            //cout<<l<<" "<<idx<<" "<<idfrom<<endl;
            //cout<<"swap "<<idx<<" "<<idfrom<<endl;
            p[j] = idx,q[j] = idfrom;
            if(notvalid == 0)
                return 1;
        }
        //for(int i=0;i<n;i++)
        //    cout<<a[i]<<" ";
        return 0;
}
 
int findSwapPairs(int N, int A[], int M, int X[], int Y[], int p[], int q[]){
    n = N;
    m = M;
    bool tr = 1;
    for(int i=0;i<n;i++){
        a[i] = A[i];
        pos[ a[i] ] = i;
        origin[i] = a[i];
        if(a[i] != i)
            tr = 0;
    }
    if(tr)
        return 0;
 
    for(int i=0;i<m;i++)
        x[i] = X[i],y[i] = Y[i];
 
    int l = 0 , r = m-1;
    while(r-l>1){
        if(check(mid,p,q))
            r = mid;
        else
            l = mid;
    }
    if(check(0,p,q))
        r = 0;
    check(r,p,q);
    return r+1;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 660 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 660 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 4 ms 632 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Correct 374 ms 24344 KB Output is correct
16 Correct 516 ms 25436 KB Output is correct
17 Correct 642 ms 26832 KB Output is correct
18 Correct 46 ms 15608 KB Output is correct
19 Correct 342 ms 26272 KB Output is correct
20 Correct 366 ms 26872 KB Output is correct
21 Correct 350 ms 26980 KB Output is correct
22 Correct 364 ms 21628 KB Output is correct
23 Correct 374 ms 27896 KB Output is correct
24 Correct 638 ms 27512 KB Output is correct
25 Correct 619 ms 27128 KB Output is correct
26 Correct 431 ms 26872 KB Output is correct
27 Correct 422 ms 26360 KB Output is correct
28 Correct 617 ms 27384 KB Output is correct
29 Correct 603 ms 26872 KB Output is correct
30 Correct 330 ms 25936 KB Output is correct
31 Correct 585 ms 27516 KB Output is correct
32 Correct 396 ms 26488 KB Output is correct
33 Correct 651 ms 27512 KB Output is correct
34 Correct 528 ms 27404 KB Output is correct
35 Correct 346 ms 25848 KB Output is correct
36 Correct 90 ms 24568 KB Output is correct
37 Correct 560 ms 28280 KB Output is correct
38 Correct 541 ms 27256 KB Output is correct
39 Correct 558 ms 27256 KB Output is correct