oj.uz

Submission #31008

# Submission time Handle Problem Language Result Execution time Memory
31008 2017-08-04T00:44:14 Z kajebiii Sorting (IOI15_sorting) C++14
100 / 100
 528 ms 13816 KB 
#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 2e5 + 100;

int N, M, *S, *X, *Y, *P, *Q;
int Now[MAX_N], To[MAX_N], NowR[MAX_N], ToR[MAX_N];
int sortIx;
bool isSort() {
    while(sortIx < N && NowR[sortIx] == ToR[sortIx]) sortIx++;
//    printf("sortIx : %d\n", sortIx);
    return sortIx == N;
}
bool isCan(int m) {
    sortIx = 0;
    for(int i=0; i<N; i++) Now[i] = S[i], To[i] = i;
    for(int i=0; i<N; i++) NowR[Now[i]] = i, ToR[To[i]] = i;
    for(int i=m-1; i>=0; i--) {
        int x = X[i], y = Y[i];
        swap(ToR[To[x]], ToR[To[y]]);
        swap(To[x], To[y]);
    }
    for(int i=0; i<m; i++) P[i] = 0, Q[i] = 0;
    
//    printf("%d start\n", m);
//    printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
//    printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]);  puts("");
    if(isSort()) return true;
    for(int i=0; i<m; i++) {
        int x = X[i], y = Y[i];
        swap(ToR[To[x]], ToR[To[y]]);
        swap(To[x], To[y]);
        swap(NowR[Now[x]], NowR[Now[y]]);
        swap(Now[x], Now[y]);

        int l = NowR[sortIx], r = ToR[sortIx];
        swap(NowR[Now[l]], NowR[Now[r]]);
        swap(Now[l], Now[r]);
        P[i] = l; Q[i] = r;
//        printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
//        printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]);  puts("");
        if(isSort()) return true;
    }
    return false;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    N = n; M = m; S = s; X = x; Y = y; P = p; Q = q;
    int ans = -1;
    for(int l=0, r=M; l<=r; ) {
        int m = (l+r) >> 1;
        if(isCan(m)) ans = m, r = m-1; else l = m+1;
    }
    isCan(ans);
    return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66:13: warning: declaration of 'int m' shadows a parameter [-Wshadow]
         int m = (l+r) >> 1;
             ^
sorting.cpp:62:39: note: shadowed declaration is here
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                       ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 320 ms 12408 KB Output is correct
16 Correct 438 ms 12664 KB Output is correct
17 Correct 527 ms 13240 KB Output is correct
18 Correct 99 ms 10488 KB Output is correct
19 Correct 259 ms 12372 KB Output is correct
20 Correct 283 ms 12536 KB Output is correct
21 Correct 244 ms 12664 KB Output is correct
22 Correct 298 ms 13432 KB Output is correct
23 Correct 294 ms 13688 KB Output is correct
24 Correct 528 ms 13560 KB Output is correct
25 Correct 455 ms 13304 KB Output is correct
26 Correct 370 ms 12536 KB Output is correct
27 Correct 321 ms 12280 KB Output is correct
28 Correct 460 ms 13432 KB Output is correct
29 Correct 353 ms 13148 KB Output is correct
30 Correct 265 ms 11768 KB Output is correct
31 Correct 493 ms 13432 KB Output is correct
32 Correct 294 ms 13304 KB Output is correct
33 Correct 498 ms 13560 KB Output is correct
34 Correct 340 ms 13520 KB Output is correct
35 Correct 249 ms 12152 KB Output is correct
36 Correct 61 ms 11256 KB Output is correct
37 Correct 460 ms 13816 KB Output is correct
38 Correct 344 ms 13304 KB Output is correct
39 Correct 412 ms 13432 KB Output is correct