oj.uz

Submission #794136

# Submission time Handle Problem Language Result Execution time Memory
794136 2023-07-26T09:45:08 Z PixelCat Sorting (IOI15_sorting) C++14
36 / 100
 99 ms 133400 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[]) {
    bool pote = true;
    For(i, 0, N - 1) {
        val[i] = S[i];
        pos[val[i]] = i;
        if(S[i] != i) pote = false;
    }
    if(pote) return 0;

    // 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 - 1, 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 27 ms 56696 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Correct 29 ms 61268 KB Output is correct
4 Correct 28 ms 61372 KB Output is correct
5 Correct 31 ms 61268 KB Output is correct
6 Correct 31 ms 61340 KB Output is correct
7 Correct 30 ms 61372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56696 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Correct 29 ms 61268 KB Output is correct
4 Correct 28 ms 61372 KB Output is correct
5 Correct 31 ms 61268 KB Output is correct
6 Correct 31 ms 61340 KB Output is correct
7 Correct 30 ms 61372 KB Output is correct
8 Correct 29 ms 56656 KB Output is correct
9 Correct 28 ms 56676 KB Output is correct
10 Correct 31 ms 61508 KB Output is correct
11 Correct 31 ms 61536 KB Output is correct
12 Correct 31 ms 61520 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 56676 KB Output is correct
2 Correct 30 ms 61268 KB Output is correct
3 Correct 31 ms 61524 KB Output is correct
4 Correct 31 ms 61552 KB Output is correct
5 Correct 31 ms 61488 KB Output is correct
6 Correct 31 ms 61328 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56696 KB Output is correct
2 Correct 29 ms 56652 KB Output is correct
3 Correct 29 ms 61268 KB Output is correct
4 Correct 28 ms 61372 KB Output is correct
5 Correct 31 ms 61268 KB Output is correct
6 Correct 31 ms 61340 KB Output is correct
7 Correct 30 ms 61372 KB Output is correct
8 Correct 29 ms 56656 KB Output is correct
9 Correct 28 ms 56676 KB Output is correct
10 Correct 31 ms 61508 KB Output is correct
11 Correct 31 ms 61536 KB Output is correct
12 Correct 31 ms 61520 KB Output is correct
13 Correct 28 ms 56676 KB Output is correct
14 Correct 30 ms 61268 KB Output is correct
15 Correct 31 ms 61524 KB Output is correct
16 Correct 31 ms 61552 KB Output is correct
17 Correct 31 ms 61488 KB Output is correct
18 Correct 31 ms 61328 KB Output is correct
19 Correct 28 ms 56604 KB Output is correct
20 Correct 29 ms 56744 KB Output is correct
21 Correct 47 ms 65804 KB Output is correct
22 Correct 50 ms 65804 KB Output is correct
23 Runtime error 99 ms 133400 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 63044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 63044 KB Output isn't correct
2 Halted 0 ms 0 KB -