제출 #366688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366688		mjhmjh1104	정렬하기 (IOI15_sorting)	C++14	100 / 100	464 ms	23140 KiB

sorting

#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 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26