제출 #794142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794142		PixelCat	정렬하기 (IOI15_sorting)	C++14	54 / 100	49 ms	65860 KiB

sorting

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

#include "sorting.h"

#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) {
        memset(p, 0, sizeof(p));
        memset(sz, 0, sizeof(sz));
        blk = n;
        hist.clear();
    }
    int find(int n) {
        if(!p[n]) return n;
        return find(p[n]);
    }
    void uni(int a, int b) {
        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] = 0;
        sz[a] -= sz[b] + 1;
        blk++;
    }
} dsu;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    vector<pii> ops[MAXM * 4 + 10];
    int ans;
    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) {
        for(auto &p:ops[id]) dsu.uni(p.F, p.S);
        if(l == r) {
            if(N - dsu.blk <= l) ans = min(ans, l);
        } 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 out(int n) {
    cerr << "out:\n";
    cerr << "  "; For(i, 0, n - 1) cerr << val[i] << " \n"[i == n - 1];
    cerr << "  "; For(i, 0, n - 1) cerr << pos[i] << " \n"[i == n - 1];
}

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

    // add edges to segment tree
    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]));
    }

    // traverse through segment tree
    seg.ans = M + 1;
    dsu.init(N);
    seg.traverse(0, 0, M, N);
    
    // 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]);
    }

    // construct answer
    vector<pii> op;
    assert(check(N, seg.ans, op));
    For(j, sz(op), seg.ans - 1) P[j] = Q[j] = 0;
    Forr(j, seg.ans - 1, 0) {
        if(j < sz(op)) {
            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]);
    }
    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: 0 / 20
• Subtask 6: 0 / 26