#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
void create_circuit(int m, vector<int> a) {
int n = a.size();
int reidx[m + 1];
for (int i = 1; i <= m; i++) reidx[i] = 0;
for (int x : a) reidx[x] = 1;
int base = 0;
for (int i = 1; i <= m; i++) {
if (reidx[i]) reidx[i] = ++base;
}
vector<int> C(m + 1);
C[0] = a[0];
for (int i = 1; i <= m; i++) {
C[i] = -reidx[i];
}
vector<int> sto[base + 1];
for (int i = 1; i < n; i++) {
sto[reidx[a[i - 1]]].pb(reidx[a[i]]);
}
sto[reidx[a[n - 1]]].pb(0);
// for (int i = 1; i <= m; i++) cerr << reidx[i] << ' ';
// cerr << endl;
// for (int i = 1; i <= base; i++) {
// for (int x : sto[i]) cerr << x << ' ';
// cerr << endl;
// }
vector<pii> nxt;
vector<int> access;
vector<bool> state;
auto recur = [&](auto&& self, int ptr, int dep, int rem) -> int {
if (rem <= 0) {
nxt[ptr] = {ptr, 0};
return 0;
}
// assign left
if (dep == 1) {
nxt[ptr].ff = -2;
rem--;
} else {
int nptr = nxt.size();
nxt[ptr].ff = nptr;
nxt.pb({-1, -1});
rem = self(self, nptr, dep - 1, rem);
}
// assign right
if (dep == 1) {
nxt[ptr].ss = -2;
rem--;
} else {
int nptr = nxt.size();
nxt[ptr].ss = nptr;
nxt.pb({-1, -1});
rem = self(self, nptr, dep - 1, rem);
}
return rem;
};
auto gen = [&](auto&& self, int sz) -> int {
int logsz = 1;
while ((1 << logsz) < sz) logsz++;
nxt = {{-1, -1}};
recur(recur, 0, logsz, sz);
int used = nxt.size();
int dirs = used;
state.resize(used, 0);
access.clear();
int cnt = 0;
// cerr << "Gen size " << sz << ":\n";
// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
// cerr << "End" << endl;
do {
int st = 0;
while (true) {
if (!state[st]) {
state[st] = !state[st]; cnt++;
if (nxt[st].ff == -2) {
nxt[st].ff = dirs++;
break;
} else {
st = nxt[st].ff;
}
} else {
state[st] = !state[st]; cnt--;
if (nxt[st].ss == -2) {
nxt[st].ss = dirs++;
break;
} else {
st = nxt[st].ss;
}
}
}
} while (cnt > 0);
int intend = dirs - sz;
for (pii &cur : nxt) {
if (cur.ff >= used && cur.ff < intend) cur.ff = 0;
if (cur.ss >= used && cur.ss < intend) cur.ss = 0;
}
return intend;
};
vector<int> X(base), Y(base);
int cnt = base;
for (int i = 1; i <= base; i++) {
if (sto[i].size() == 1) {
X[i - 1] = -i;
Y[i - 1] = sto[i].front();
continue;
}
int assign = gen(gen, sto[i].size());
auto decrypt = [&](int x) -> int {
if (x == 0) return -i;
else if (x < assign) return -(x + cnt);
else return sto[i][x - assign];
};
// cerr << "Gen " << i << ": \n";
// cerr << assign << endl;
// for (pii cur : nxt) cerr << cur.ff << ' ' << cur.ss << endl;
// cerr << "End of gen " << i << endl;
X[i - 1] = decrypt(nxt[0].ff); Y[i - 1] = decrypt(nxt[0].ss);
for (int j = 1; j < (int)(nxt.size()); j++) {
// cerr << "decrypt " << nxt[j].ff << ' ' << decrypt(nxt[j].ff) << endl;
X.pb(decrypt(nxt[j].ff));
Y.pb(decrypt(nxt[j].ss));
}
cnt = (int)(X.size());
}
answer(C, X, Y);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
7916 KB |
wrong motion |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
7916 KB |
wrong motion |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
7916 KB |
wrong motion |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
