| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 237827 | Jatana | 자동 인형 (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <iostream>
#define le(v) ((int)v.size())
#define pb push_back
using namespace std;
vector<int> X, Y;
int go(int depth) {
int id = le(X);
X.pb(-1e9); Y.pb(-1e9);
if (depth > 0) {
X[id] = go(depth - 1);
Y[id] = go(depth - 1);
}
return -(id + 1);
}
void create_circuit(int M, vector<int> A) {
X.clear(); Y.clear();
int N = A.size();
vector<vector<int>> after(M + 1);
vector<int> wait(M + 1);
A.pb(0);
for (int i = 0; i < le(A) - 1; i++) {
after[A[i]].pb(A[i + 1]);
}
A.pop_back();
vector<int> C(M + 1);
C[0] = A[0];
for (int i = 1; i <= M; i++) {
if (!after[i].empty()) {
if (le(after[i]) == 1) {
C[i] = after[i][0];
} else {
int sz = le(after[i]);
int t = ((31 - __builtin_clz(sz)));
if ((1 << t) < sz) t++;
wait[i] = (1 << t) - sz;
C[i] = go(t - 1);
}
}
reverse(after[i].begin(), after[i].end());
}
int cur = C[0];
int real = -1;
while (cur) {
// cerr << cur << " ";
if (cur > 0) {
real = cur;
cur = C[cur];
} else {
cur = (-cur) - 1;
if (X[cur] == -1e9) {
if (wait[real]) {
wait[real]--;
X[cur] = C[real];
} else {
X[cur] = after[real].back();
after[real].pop_back();
}
}
swap(X[cur], Y[cur]);
cur = Y[cur];
}
}
answer(C, X, Y);
}