oj.uz

Submission #366688

# Submission time Handle Problem Language Result Execution time Memory
366688 2021-02-15T02:34:22 Z mjhmjh1104 Sorting (IOI15_sorting) C++14
100 / 100
 464 ms 23140 KB 
#include "sorting.h"
#include <cstdio>
#include <algorithm>
using namespace std;

int tree[200006], tree_cnt[524288];

int query(int i, int b, int e) {
    if (b == e) return b;
    int m = (b + e) / 2;
    if (tree_cnt[i * 2 + 1] < m - b + 1) return query(i * 2 + 1, b, m);
    else return query(i * 2 + 2, m + 1, e);
}

int update(int i, int b, int e, int p, int v) {
    if (p < b || e < p) return tree_cnt[i];
    if (b == e) return tree_cnt[i] = v;
    int m = (b + e) / 2;
    return tree_cnt[i] = update(i * 2 + 1, b, m, p, v) + update(i * 2 + 2, m + 1, e, p, v);
}

int curr[200006], curr_rev[200006];
bool visited[200006];

int getCycle(int n) {
    int cnt = 0;
    for (int i = 0; i < n; i++) visited[i] = false;
    for (int i = 0; i < n; i++) if (!visited[i]) {
        int j = curr[i];
        visited[i] = true;
        while (j != i) {
            visited[j] = true;
            j = curr[j];
        }
        cnt++;
    }
    return cnt;
}

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    auto f = [&](int z) {
        for (int i = 0; i < n; i++) curr[i] = s[i];
        for (int t = 0; t < z; t++) swap(curr[x[t]], curr[y[t]]);
        return n - getCycle(n);
    };
    int l = 0, r = m;
    while (l < r) {
        int mid = (l + r) / 2;
        if (f(mid) <= mid) r = mid;
        else l = mid + 1;
    }

    for (int i = 0; i < n; i++) tree[i] = s[i], curr[i] = curr_rev[i] = i;
    for (int i = 0; i < l; i++) swap(tree[x[i]], tree[y[i]]);
    for (int i = 0; i < n; i++) tree_cnt[262143 + i] = tree[i] == i;
    for (int i = 262142; i >= 0; i--) tree_cnt[i] = tree_cnt[i * 2 + 1] + tree_cnt[i * 2 + 2];
    for (int t = l - 1; t >= 0; t--) {
        int it = query(0, 0, 262143);
        if (it == n) break;
        p[t] = curr_rev[tree[it]];
        q[t] = it;
        update(0, 0, 262143, it, 1);
        swap(curr[p[t]], curr[q[t]]);
        swap(curr_rev[curr[p[t]]], curr_rev[curr[q[t]]]);
        if (curr[p[t]] == tree[p[t]]) update(0, 0, 262143, p[t], 1);
        swap(curr[x[t]], curr[y[t]]);
        swap(curr_rev[curr[x[t]]], curr_rev[curr[y[t]]]);
        swap(tree[x[t]], tree[y[t]]);
        int tmp = tree_cnt[262143 + x[t]];
        update(0, 0, 262143, x[t], tree_cnt[262143 + y[t]]);
        update(0, 0, 262143, y[t], tmp);
    }

    return l;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1516 KB Output is correct
2 Correct 6 ms 1516 KB Output is correct
3 Correct 5 ms 1516 KB Output is correct
4 Correct 2 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1528 KB Output is correct
7 Correct 4 ms 1516 KB Output is correct
8 Correct 4 ms 1516 KB Output is correct
9 Correct 4 ms 1536 KB Output is correct
10 Correct 4 ms 1516 KB Output is correct
11 Correct 4 ms 1528 KB Output is correct
12 Correct 5 ms 1516 KB Output is correct
13 Correct 5 ms 1516 KB Output is correct
14 Correct 2 ms 1516 KB Output is correct
15 Correct 328 ms 20460 KB Output is correct
16 Correct 351 ms 21024 KB Output is correct
17 Correct 414 ms 21996 KB Output is correct
18 Correct 72 ms 17644 KB Output is correct
19 Correct 252 ms 20460 KB Output is correct
20 Correct 287 ms 21100 KB Output is correct
21 Correct 281 ms 21228 KB Output is correct
22 Correct 303 ms 17516 KB Output is correct
23 Correct 355 ms 22928 KB Output is correct
24 Correct 400 ms 22508 KB Output is correct
25 Correct 445 ms 22164 KB Output is correct
26 Correct 267 ms 21100 KB Output is correct
27 Correct 245 ms 20460 KB Output is correct
28 Correct 406 ms 22508 KB Output is correct
29 Correct 383 ms 21740 KB Output is correct
30 Correct 178 ms 19692 KB Output is correct
31 Correct 394 ms 22252 KB Output is correct
32 Correct 353 ms 22204 KB Output is correct
33 Correct 426 ms 22508 KB Output is correct
34 Correct 385 ms 22496 KB Output is correct
35 Correct 264 ms 20332 KB Output is correct
36 Correct 54 ms 18668 KB Output is correct
37 Correct 430 ms 23140 KB Output is correct
38 Correct 464 ms 22380 KB Output is correct
39 Correct 432 ms 22380 KB Output is correct