| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 794154 |
2023-07-26T09:56:59 Z |
PixelCat |
Sorting (IOI15_sorting) |
C++14 |
|
111 ms |
127500 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 init(int m) {
ans = m + 1;
For(i, 0, MAXM * 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) {
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;
}
int32_t findSwapPairs2(int32_t N, int32_t S[], int32_t M, int32_t X[], int32_t Y[]) {
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;
For(i, 0, M - 1) {
int p1 = X[i], p2 = Y[i];
swap(pos[val[p1]], pos[val[p2]]);
swap(val[p1], val[p2]);
vector<pii> op;
if(check(N, i + 1, op)) {
return (int32_t)(i + 1);
}
}
assert(false);
return 0;
}
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.init(M);
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]);
}
assert(seg.ans == findSwapPairs2(N, S, M, X, Y));
// 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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
61336 KB |
Output is correct |
| 2 |
Correct |
32 ms |
61324 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
124232 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
61336 KB |
Output is correct |
| 2 |
Correct |
32 ms |
61324 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
124232 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
61296 KB |
Output is correct |
| 2 |
Runtime error |
77 ms |
124256 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
61336 KB |
Output is correct |
| 2 |
Correct |
32 ms |
61324 KB |
Output is correct |
| 3 |
Runtime error |
78 ms |
124232 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
127500 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
127500 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
