oj.uz

Submission #794142

# Submission time Handle Problem Language Result Execution time Memory
794142 2023-07-26T09:47:43 Z PixelCat Sorting (IOI15_sorting) C++14
54 / 100
 49 ms 65860 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61268 KB Output is correct
2 Correct 27 ms 61360 KB Output is correct
3 Correct 25 ms 61380 KB Output is correct
4 Correct 27 ms 61356 KB Output is correct
5 Correct 31 ms 61360 KB Output is correct
6 Correct 27 ms 61268 KB Output is correct
7 Correct 34 ms 61260 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61268 KB Output is correct
2 Correct 27 ms 61360 KB Output is correct
3 Correct 25 ms 61380 KB Output is correct
4 Correct 27 ms 61356 KB Output is correct
5 Correct 31 ms 61360 KB Output is correct
6 Correct 27 ms 61268 KB Output is correct
7 Correct 34 ms 61260 KB Output is correct
8 Correct 30 ms 61372 KB Output is correct
9 Correct 33 ms 61268 KB Output is correct
10 Correct 27 ms 61480 KB Output is correct
11 Correct 26 ms 61524 KB Output is correct
12 Correct 26 ms 61560 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61380 KB Output is correct
2 Correct 33 ms 61284 KB Output is correct
3 Correct 28 ms 61492 KB Output is correct
4 Correct 27 ms 61548 KB Output is correct
5 Correct 28 ms 61524 KB Output is correct
6 Correct 27 ms 61288 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61268 KB Output is correct
2 Correct 27 ms 61360 KB Output is correct
3 Correct 25 ms 61380 KB Output is correct
4 Correct 27 ms 61356 KB Output is correct
5 Correct 31 ms 61360 KB Output is correct
6 Correct 27 ms 61268 KB Output is correct
7 Correct 34 ms 61260 KB Output is correct
8 Correct 30 ms 61372 KB Output is correct
9 Correct 33 ms 61268 KB Output is correct
10 Correct 27 ms 61480 KB Output is correct
11 Correct 26 ms 61524 KB Output is correct
12 Correct 26 ms 61560 KB Output is correct
13 Correct 32 ms 61380 KB Output is correct
14 Correct 33 ms 61284 KB Output is correct
15 Correct 28 ms 61492 KB Output is correct
16 Correct 27 ms 61548 KB Output is correct
17 Correct 28 ms 61524 KB Output is correct
18 Correct 27 ms 61288 KB Output is correct
19 Correct 27 ms 61388 KB Output is correct
20 Correct 28 ms 61296 KB Output is correct
21 Correct 49 ms 65704 KB Output is correct
22 Correct 43 ms 65720 KB Output is correct
23 Correct 44 ms 65808 KB Output is correct
24 Correct 44 ms 65488 KB Output is correct
25 Correct 42 ms 65860 KB Output is correct
26 Correct 49 ms 65792 KB Output is correct
27 Correct 45 ms 65720 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62972 KB Output is correct
2 Incorrect 36 ms 62120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62972 KB Output is correct
2 Incorrect 36 ms 62120 KB Output isn't correct
3 Halted 0 ms 0 KB -