oj.uz

Submission #519162

# Submission time Handle Problem Language Result Execution time Memory
519162 2022-01-25T19:00:00 Z tabr Sorting (IOI15_sorting) C++17
100 / 100
 329 ms 14496 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int low = -1;
    int high = m + 1;
    while (high - low > 1) {
        int mid = (high + low) >> 1;
        vector<int> t(n);
        for (int i = 0; i < n; i++) {
            t[i] = s[i];
        }
        for (int i = 0; i < mid; i++) {
            swap(t[x[i]], t[y[i]]);
        }
        vector<pair<int, int>> a;
        vector<int> pos(n);
        for (int i = 0; i < n; i++) {
            pos[t[i]] = i;
        }
        for (int i = 0; i < n; i++) {
            if (t[i] == i) {
                continue;
            }
            int j = pos[i];
            a.emplace_back(t[i], t[j]);
            swap(t[i], t[j]);
            swap(pos[t[i]], pos[t[j]]);
        }
        if ((int) a.size() <= mid) {
            for (int i = 0; i < n; i++) {
                t[i] = s[i];
                pos[t[i]] = i;
            }
            for (int i = 0; i < mid; i++) {
                swap(t[x[i]], t[y[i]]);
                swap(pos[t[x[i]]], pos[t[y[i]]]);
                if (i >= (int) a.size()) {
                    p[i] = q[i] = 0;
                } else {
                    p[i] = pos[a[i].first];
                    q[i] = pos[a[i].second];
                    swap(t[p[i]], t[q[i]]);
                    swap(pos[t[p[i]]], pos[t[q[i]]]);
                }
            }
            high = mid;
        } else {
            low = mid;
        }
    }
    return high;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 1 ms 292 KB Output is correct
17 Correct 1 ms 280 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 1 ms 540 KB Output is correct
22 Correct 2 ms 544 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 2 ms 552 KB Output is correct
25 Correct 1 ms 544 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 1 ms 460 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 412 KB Output is correct
7 Correct 2 ms 428 KB Output is correct
8 Correct 2 ms 428 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 428 KB Output is correct
11 Correct 2 ms 408 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 1 ms 336 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 424 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 1 ms 412 KB Output is correct
7 Correct 2 ms 428 KB Output is correct
8 Correct 2 ms 428 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 428 KB Output is correct
11 Correct 2 ms 408 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 231 ms 13168 KB Output is correct
16 Correct 270 ms 13332 KB Output is correct
17 Correct 294 ms 13972 KB Output is correct
18 Correct 99 ms 12924 KB Output is correct
19 Correct 189 ms 13636 KB Output is correct
20 Correct 208 ms 13984 KB Output is correct
21 Correct 195 ms 13944 KB Output is correct
22 Correct 231 ms 13576 KB Output is correct
23 Correct 266 ms 14496 KB Output is correct
24 Correct 312 ms 14200 KB Output is correct
25 Correct 325 ms 13892 KB Output is correct
26 Correct 207 ms 12688 KB Output is correct
27 Correct 188 ms 12288 KB Output is correct
28 Correct 266 ms 14084 KB Output is correct
29 Correct 290 ms 13796 KB Output is correct
30 Correct 146 ms 11664 KB Output is correct
31 Correct 314 ms 14040 KB Output is correct
32 Correct 263 ms 13908 KB Output is correct
33 Correct 329 ms 14068 KB Output is correct
34 Correct 278 ms 14128 KB Output is correct
35 Correct 197 ms 13532 KB Output is correct
36 Correct 78 ms 10816 KB Output is correct
37 Correct 315 ms 14480 KB Output is correct
38 Correct 301 ms 13892 KB Output is correct
39 Correct 307 ms 14004 KB Output is correct