oj.uz

Submission #126905

# Submission time Handle Problem Language Result Execution time Memory
126905 2019-07-08T15:16:21 Z Plurm Sorting (IOI15_sorting) C++11
100 / 100
 644 ms 23804 KB 
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

int target[200005];
int cur[200005];
int bck[200005];
vector<pair<int,int> > computeShortestSwaps(int N, int t[]){
    vector<pair<int,int> > ret;
    for(int i = 0; i < N; i++){
        bck[i] = i;
        cur[i] = i;
    }
    for(int i = 0; i < N; i++){
        if(cur[i] != t[i]){
            int idx1 = i;
            int idx2 = bck[t[i]];
            ret.emplace_back(idx1, idx2);
            bck[cur[idx1]] = idx2;
            bck[cur[idx2]] = idx1;
            swap(cur[idx1], cur[idx2]);
        }
    }
    return ret;
}
int aux[200005];
bool solve(int N, int mid, int S[], int X[], int Y[], int P[], int Q[]){
    for(int i = 0; i < N; i++) cur[i] = i;
    for(int i = 0; i < mid; i++){
        swap(cur[X[i]], cur[Y[i]]);
    }
    for(int i = 0; i < N; i++) bck[cur[i]] = i;
    for(int i = 0; i < N; i++) target[i] = cur[S[i]];
    vector<pair<int,int> > cmds = computeShortestSwaps(N, target);
    if(cmds.size() > mid) return false;
    for(int i = 0; i < N; i++){
        cur[i] = i;
        bck[i] = i;
        aux[i] = i;
        target[i] = i;
    }
    for(int i = 0; i < mid; i++){
        int idx1 = X[i];
        int idx2 = Y[i];
        bck[cur[idx1]] = idx2;
        bck[cur[idx2]] = idx1;
        swap(cur[idx1], cur[idx2]);
        if(i < cmds.size()){
            idx1 = target[cmds[i].first];
            idx2 = target[cmds[i].second];
            target[aux[idx1]] = idx2;
            target[aux[idx2]] = idx1;
            swap(aux[idx1], aux[idx2]);
            idx1 = bck[idx1];
            idx2 = bck[idx2];
            P[i] = idx1;
            Q[i] = idx2;
        }else{
            P[i] = 0;
            Q[i] = 0;
        }
    }
    return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int lo = 0;
    int hi = M;
    int mid;
    while(lo < hi){
        mid = (lo + hi)/2;
        if(solve(N, mid, S, X, Y, P, Q)){
            hi = mid;
        }else{
            lo = mid+1;
        }
    }
    solve(N, lo, S, X, Y, P, Q);
    return lo;
}

Compilation message

sorting.cpp: In function 'bool solve(int, int, int*, int*, int*, int*, int*)':
sorting.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cmds.size() > mid) return false;
        ~~~~~~~~~~~~^~~~~
sorting.cpp:48:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < cmds.size()){
            ~~^~~~~~~~~~~~~

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 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 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 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 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 2 ms 380 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 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

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 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 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 2 ms 380 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 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 632 KB Output is correct
22 Correct 3 ms 632 KB Output is correct
23 Correct 4 ms 632 KB Output is correct
24 Correct 4 ms 632 KB Output is correct
25 Correct 3 ms 636 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 3 ms 632 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 5 ms 632 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 760 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 5 ms 632 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 760 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 467 ms 21176 KB Output is correct
16 Correct 482 ms 21612 KB Output is correct
17 Correct 582 ms 22828 KB Output is correct
18 Correct 165 ms 21648 KB Output is correct
19 Correct 372 ms 22884 KB Output is correct
20 Correct 356 ms 23472 KB Output is correct
21 Correct 333 ms 23344 KB Output is correct
22 Correct 459 ms 18244 KB Output is correct
23 Correct 528 ms 23664 KB Output is correct
24 Correct 602 ms 23388 KB Output is correct
25 Correct 552 ms 23132 KB Output is correct
26 Correct 394 ms 22012 KB Output is correct
27 Correct 375 ms 21452 KB Output is correct
28 Correct 610 ms 23284 KB Output is correct
29 Correct 542 ms 22860 KB Output is correct
30 Correct 263 ms 20848 KB Output is correct
31 Correct 581 ms 23316 KB Output is correct
32 Correct 464 ms 22856 KB Output is correct
33 Correct 644 ms 23296 KB Output is correct
34 Correct 582 ms 23048 KB Output is correct
35 Correct 361 ms 22556 KB Output is correct
36 Correct 94 ms 19832 KB Output is correct
37 Correct 586 ms 23804 KB Output is correct
38 Correct 523 ms 23156 KB Output is correct
39 Correct 606 ms 23268 KB Output is correct