#include "doll.h"
#include <iostream>
#include <algorithm>
#include <cassert>
#include <random>
#include <map>
#define le(v) ((int)v.size())
#define pb push_back
using namespace std;
vector<int> X, Y;
int inc = 0;
int go(int outs) {
int id = le(X);
X.pb(-1e9); Y.pb(-1e9);
if (outs > 2) {
if (outs & 1) {
outs++;
inc++;
}
X[id] = go(outs / 2);
Y[id] = go(outs / 2);
} else assert(outs == 2);
return -(id + 1);
}
vector<int> gen(int k) {
if (k == 0) return {0};
vector<int> sub = gen(k - 1);
vector<int> real;
for (int i = 0; i < le(sub); i++) {
real.pb(sub[i]);
real.pb(sub[i] + (1 << (k - 1)));
}
return real;
}
vector<int> inv(vector<int> p) {
vector<int> q(le(p));
for (int i = 0; i < le(p); i++) {
q[p[i]] = i;
}
return q;
}
mt19937 rng(1337);
void create_circuit(int M, vector<int> A) {
X.clear(); Y.clear();
int N = A.size();
int cur = A[0];
A.insert(A.begin(), 0);
map<int, int> cnt;
for (int i = 0; i < le(A); i++) {
cnt[A[i]]++;
}
vector<int> C(M + 1, -1e9);
vector<int> B;
int sz = 0;
for (int i = 0; i < le(A); i++) {
if (cnt[A[i]] == 1) {
C[A[i]] = (i + 1 < le(A)) ? A[i + 1] : 0;
} else {
sz++;
B.pb((i + 1 < le(A)) ? A[i + 1] : 0);
}
}
inc = 0;
int root = go(max(sz, 2));
if (B.empty()) {
for (int i = 0; i < le(C); i++) {
if (C[i] == -1e9) C[i] = 0;
}
for (int x : C) {
cerr << x << " ";
}
cerr << endl;
answer(C, {}, {});
return;
}
for (int i = 0; i < le(C); i++) {
if (C[i] == -1e9) C[i] = root;
}
int wait = inc;
A = B;
reverse(A.begin(), A.end());
while (cur) {
cerr << cur << " ";
if (cur > 0) {
cur = C[cur];
} else {
cur = (-cur) - 1;
if (X[cur] == -1e9) {
bool cond = (wait + le(A)) % 2;
// bool cond = true;
// bool cond = binary_search(order[real].begin(), order[real].end(), it[real]);
if (wait
&& ((le(A) == 1) || cond)) {
wait--;
X[cur] = root;
} else {
// cout << "decide" << endl;
X[cur] = A.back();
A.pop_back();
}
}
swap(X[cur], Y[cur]);
cur = Y[cur];
}
}
cerr << endl;
for (int x : C) {
cerr << x << " ";
}
cerr << endl;
for (int i = 0; i < le(X); i++) {
cerr << X[i] << " " << Y[i] << endl;
}
answer(C, X, Y);
return;
vector<bool> del(le(X), false);
for (int it = 0; it < 100; it++) {
for (int i = 0; i < le(X); i++) {
if (del[i]) continue;
if (X[i] < 0) {
int j = (-X[i]) - 1;
if (X[j] == Y[j]) {
X[i] = X[j];
del[j] = true;
}
}
if (Y[i] < 0) {
int j = (-Y[i]) - 1;
if (X[j] == Y[j]) {
Y[i] = X[j];
del[j] = true;
}
}
}
for (int i = 0; i < le(C); i++) {
if (C[i] < 0) {
int j = (-C[i]) - 1;
if (X[j] == Y[j]) {
C[i] = X[j];
del[j] = true;
}
}
}
if (it == 0) {
int killed = 0;
for (int x : del) killed++;
// cout << "killed: " << killed << endl;
}
}
vector<int> alive;
for (int i = 0; i < le(X); i++) {
if (!del[i]) {
alive.pb(i);
}
}
for (int i = 0; i < le(X); i++) {
if (X[i] < 0) {
int id = lower_bound(alive.begin(), alive.end(), (-X[i]) - 1) - alive.begin();
X[i] = -(id + 1);
}
if (Y[i] < 0) {
int id = lower_bound(alive.begin(), alive.end(), (-Y[i]) - 1) - alive.begin();
Y[i] = -(id + 1);
}
}
for (int i = 0; i < le(C); i++) {
if (C[i] < 0) {
int id = lower_bound(alive.begin(), alive.end(), (-C[i]) - 1) - alive.begin();
C[i] = -(id + 1);
}
}
int jump = 0;
for (int i = 0; i < le(X); i++) {
if (del[i]) {
jump++;
} else {
X[i - jump] = X[i];
Y[i - jump] = Y[i];
}
}
X.resize(le(X) - jump);
Y.resize(le(Y) - jump);
// for (int x : del) {
// cout << x << " ";
// }
// cout << endl;
// for (int i = 0; i < le(X); i++) {
// cout << X[i] << " " << Y[i] << endl;
// }
answer(C, X, Y);
}
Compilation message
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:150:13: warning: unused variable 'x' [-Wunused-variable]
150 | for (int x : del) killed++;
| ^
doll.cpp:49:6: warning: unused variable 'N' [-Wunused-variable]
49 | int N = A.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
383 ms |
5520 KB |
Output is correct |
| 3 |
Correct |
263 ms |
5052 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
369 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
407 ms |
7608 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
383 ms |
5520 KB |
Output is correct |
| 3 |
Correct |
263 ms |
5052 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
369 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
407 ms |
7608 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Execution timed out |
1086 ms |
8928 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
383 ms |
5520 KB |
Output is correct |
| 3 |
Correct |
263 ms |
5052 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
369 ms |
1720 KB |
Output is correct |
| 6 |
Correct |
407 ms |
7608 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Execution timed out |
1086 ms |
8928 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
2 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
204 KB |
Output is correct |
| 7 |
Correct |
2 ms |
204 KB |
Output is correct |
| 8 |
Correct |
2 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
3 ms |
296 KB |
Output is partially correct |
| 2 |
Execution timed out |
1095 ms |
5792 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
3 ms |
296 KB |
Output is partially correct |
| 2 |
Execution timed out |
1095 ms |
5792 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
