oj.uz

Submission #245287

# Submission time Handle Problem Language Result Execution time Memory
245287 2020-07-05T23:44:20 Z ant101 Sorting (IOI15_sorting) C++14
100 / 100
 475 ms 21048 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include "sorting.h"
#include <algorithm>

using namespace std;

const int MAXN = 200005;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int lo=0, hi=m;
    
    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        vector<int> fp(n), fpidx(n), sc(s, s+n);
        for(int i=0;i<n;++i) fp[i]=i;
        
        for(int i=0;i<mid;++i){
            swap(fp[x[i]], fp[y[i]]);
        }
        for(int i=0;i<n;++i){
            fpidx[fp[i]]=i;
        }
        
        vector<int> perm(n), idx(n);
        for(int i=0;i<n;++i){
            perm[i]=i;
            idx[perm[i]]=i;
        }
        int j=0;
        for(int i=0;i<mid;++i){
            swap(sc[x[i]], sc[y[i]]);
            swap(perm[x[i]], perm[y[i]]);
            swap(idx[perm[x[i]]], idx[perm[y[i]]]);
            
            bool found=false;
            for(;j<n;j++){
                int jj=idx[j];
                if(fpidx[perm[jj]]!=sc[jj]){
                    found=true;
                    p[i]=jj;
                    q[i]=idx[fp[sc[jj]]];
                    swap(sc[p[i]], sc[q[i]]);
                    break;
                }
            }
            if(!found) p[i]=q[i]=0;
        }
        bool ok=true;
        for(int i=0;i<n;++i) if(sc[i]!=i) ok=false;
        if(ok){
            hi=mid;
        }else{
            lo=mid+1;
        }
        
    }
    vector<int> fp(n), fpidx(n), sc(s, s+n);
    for(int i=0;i<n;++i) fp[i]=i;
    
    for(int i=0;i<lo;++i){
        swap(fp[x[i]], fp[y[i]]);
    }
    for(int i=0;i<n;++i){
        fpidx[fp[i]]=i;
    }
    
    vector<int> perm(n), idx(n);
    for(int i=0;i<n;++i){
        perm[i]=i;
        idx[perm[i]]=i;
    }
    int j=0;
    for(int i=0;i<lo;++i){
        swap(sc[x[i]], sc[y[i]]);
        swap(perm[x[i]], perm[y[i]]);
        swap(idx[perm[x[i]]], idx[perm[y[i]]]);
        for(;j<n;j++){
            int jj=idx[j];
            if(fpidx[perm[jj]]!=sc[jj]){
                p[i]=jj;
                q[i]=idx[fp[sc[jj]]];
                swap(sc[p[i]], sc[q[i]]);
                break;
            }
        }
    }
    return lo;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 432 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 6 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 338 ms 18416 KB Output is correct
16 Correct 369 ms 18828 KB Output is correct
17 Correct 432 ms 19868 KB Output is correct
18 Correct 144 ms 19260 KB Output is correct
19 Correct 297 ms 20464 KB Output is correct
20 Correct 306 ms 20944 KB Output is correct
21 Correct 308 ms 20936 KB Output is correct
22 Correct 343 ms 15196 KB Output is correct
23 Correct 392 ms 20748 KB Output is correct
24 Correct 434 ms 20472 KB Output is correct
25 Correct 458 ms 20224 KB Output is correct
26 Correct 295 ms 21048 KB Output is correct
27 Correct 263 ms 20496 KB Output is correct
28 Correct 416 ms 20396 KB Output is correct
29 Correct 408 ms 20196 KB Output is correct
30 Correct 218 ms 20656 KB Output is correct
31 Correct 412 ms 20636 KB Output is correct
32 Correct 393 ms 20080 KB Output is correct
33 Correct 437 ms 20288 KB Output is correct
34 Correct 418 ms 20392 KB Output is correct
35 Correct 295 ms 20180 KB Output is correct
36 Correct 115 ms 20644 KB Output is correct
37 Correct 475 ms 21048 KB Output is correct
38 Correct 428 ms 20072 KB Output is correct
39 Correct 428 ms 20216 KB Output is correct