Submission #794200

#	Time	Username	Problem	Language	Result	Execution time	Memory
794200		PixelCat	Sorting (IOI15_sorting)	C++14	100 / 100	830 ms	180900 KiB

sorting

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "sorting.h"

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
const int MAXM = 3 * MAXN;

struct DSU {
    int p[MAXN + 10];
    int sz[MAXN + 10];
    int blk;
    vector<pii> hist;
    void init(int n) {
        // cerr << "dsu init!\n";
        memset(p, -1, sizeof(p));
        memset(sz, 0, sizeof(sz));
        blk = n;
        hist.clear();
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return find(p[n]);
    }
    void uni(int a, int b) {
        // cerr << "dsu uni " << a << " " << b << "\n";
        a = find(a); b = find(b);
        if(a == b) {
            hist.eb(-1, -1);
            return;
        }
        if(sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b] + 1;
        blk--;
        hist.eb(a, b);
    }
    void undo() {
        int a, b;
        tie(a, b) = hist.back();
        hist.pop_back();
        if(a < 0) return;
        p[b] = -1;
        sz[a] -= sz[b] + 1;
        blk++;
    }
} dsu;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    vector<pii> ops[MAXN * 4 + 10];
    int ans;
    void init(int m) {
        ans = m + 1;
        For(i, 0, MAXN * 4 + 10 - 1) {
            ops[i].clear();
        }
    }
    void add(int id, int l, int r, int L, int R, pii p) {
        if(l > R || r < L) return;
        if(l >= L && r <= R) {
            ops[id].eb(p);
            return;
        }
        int m = (l + r) / 2;
        if(L <= m) add(L(id), l, m, L, R, p);
        if(R > m)  add(R(id), m + 1, r, L, R, p);
    }
    void traverse(int id, int l, int r, int N) {
        // cerr << "ops: " << id << " - " << sz(ops[id]) << "\n";
        for(auto &p:ops[id]) dsu.uni(p.F, p.S);
        if(l == r) {
            if(N - dsu.blk <= l) ans = min(ans, l);
            // cerr << "traverse: " << l << " " << dsu.blk << "\n";
        } else {
            int m = (l + r) / 2;
            traverse(L(id), l, m, N);
            traverse(R(id), m + 1, r, N);
        }
        For(_, 1, sz(ops[id])) dsu.undo();
    }
} seg;

int val[MAXN + 10];
int pos[MAXN + 10];
int last[MAXN + 10];

int tmp[MAXN + 10];
bool check(int n, int lim, vector<pii> &ops) {
    For(i, 0, n - 1) tmp[i] = val[i];
    ops.clear();
    For(i, 0, n - 1) {
        while(tmp[i] != i) {
            ops.eb(tmp[i], tmp[tmp[i]]);
            swap(tmp[i], tmp[tmp[i]]);
        }
    }
    return sz(ops) <= lim;
}

void timer() {
    static clock_t lastt = -1;
    clock_t cur = clock();
    if(lastt != -1) {
        cerr << fixed << setprecision(3);
        cerr << "elapsed: " << ((double)(cur - lastt) / CLOCKS_PER_SEC) << "\n";
    }
    lastt = cur;
}

int32_t findSwapPairs(int32_t N, int32_t S[], int32_t M, int32_t X[], int32_t Y[], int32_t P[], int32_t Q[]) {
    timer();
    
    For(i, 0, N - 1) {
        val[i] = S[i];
        pos[val[i]] = i;
    }
    timer();

    // add edges to segment tree
    M = N;
    seg.init(M);
    memset(last, -1, sizeof(last));
    For(i, 0, M - 1) {
        int p1 = X[i], p2 = Y[i];
        seg.add(0, 0, M, last[p1] + 1, i, pii(p1, val[p1]));
        seg.add(0, 0, M, last[p2] + 1, i, pii(p2, val[p2]));
        last[p1] = i; last[p2] = i;
        swap(pos[val[p1]], pos[val[p2]]);
        swap(val[p1], val[p2]);
    }
    For(i, 0, N - 1) {
        seg.add(0, 0, M, last[i] + 1, M, pii(i, val[i]));
    }
    timer();

    // traverse through segment tree
    dsu.init(N);
    seg.traverse(0, 0, M, N);
    timer();
    
    // restore states at time i
    For(i, 0, N - 1) {
        val[i] = S[i];
        pos[val[i]] = i;
    }
    For(i, 0, seg.ans - 1) {
        int p1 = X[i], p2 = Y[i];
        swap(pos[val[p1]], pos[val[p2]]);
        swap(val[p1], val[p2]);
    }
    timer();

    // construct answer
    vector<pii> op;
    assert(check(N, seg.ans, op));
    while(sz(op) < seg.ans) op.eb(0, 0);
    Forr(j, seg.ans - 1, 0) {
        int v1 = op[j].F;
        int v2 = op[j].S;
        P[j] = (int32_t)pos[v1];
        Q[j] = (int32_t)pos[v2];
        swap(val[pos[v1]], val[pos[v2]]);
        swap(pos[v1], pos[v2]);

        int p1 = X[j];
        int p2 = Y[j];
        swap(pos[val[p1]], pos[val[p2]]);
        swap(val[p1], val[p2]);
    }
    timer();
    return (int32_t)(seg.ans);
}

/*

30421
10423
10243

*/

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26