| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 636765 | tabr | 자동 인형 (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
#ifdef tabr
void answer(vector<int> c, vector<int> x, vector<int> y) {
debug(c);
debug(x);
debug(y);
}
#else
#include "doll.h"
#endif
void create_curcuit(int m, vector<int> a) {
a.emplace_back(0);
int n = (int) a.size() - 1;
int l = 31 - __builtin_clz(n);
vector<int> x(l + 1), y(l + 1);
for (int i = l; i >= 0; i--) {
int v = l - i;
if (i == 0) {
x[v] = 0;
} else {
x[v] = v + 1;
}
y[v] = 0;
if (n & (1 << i)) {
if (i == 0) {
y[v] = -1;
} else {
int z = (int) x.size();
y[v] = z;
for (int j = 0; j < (1 << i) - 1; j++) {
if (2 * j + 2 < (1 << i)) {
x.emplace_back(z + 2 * j + 1);
y.emplace_back(z + 2 * j + 2);
} else {
x.emplace_back(-1);
y.emplace_back(-1);
}
}
}
}
}
debug(x);
debug(y);
for (int i = 0; i < (int) x.size(); i++) {
x[i] = -1 - x[i];
y[i] = -1 - y[i];
}
vector<int> c(m + 1, -1);
c[0] = a[0];
int v = 0;
int cnt = 1;
vector<int> sw(x.size());
do {
if (v >= 0) {
debug(v);
v = c[v];
} else {
if (!sw[~v]) {
if (x[~v] == 0) {
x[~v] = a[cnt];
cnt++;
}
sw[~v] ^= 1;
v = x[~v];
} else {
if (y[~v] == 0) {
y[~v] = a[cnt];
cnt++;
}
sw[~v] ^= 1;
v = y[~v];
}
}
} while (v != 0);
answer(c, x, y);
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
create_curcuit(4, {1, 2, 1, 3});
return 0;
}
#endif