| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 475950 | kessido | Mechanical Doll (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <bits/stdc++.h>
const int UNASSINED = 1'000'000'000;
const int ROOT = 1'000'000'001;
using vi = std::vector<int>;
vi craete_level(const vi& last_level, vi& X, vi& Y, int& S) {
vi new_level;
for(size_t i = 0; i < last_level.size(); i++) {
if(i+1 < last_level.size()) {
X.push_back(last_level[i]);
Y.push_back(last_level[i+1]);
new_level.push_back(-1 * (++S));
}
}
return new_level;
}
int& simulate_untill_next_unassined(int cur_switch, vi& state, vi& X, vi& Y) {
while(true) {
int idx = -cur_switch - 1;
int* ptr = state[idx] ? &X[idx] : &Y[idx];
int& val = *ptr;
if(val == UNASSINED) return val;
assert(val < 0);
cur_switch = val;
}
}
void create_circuit(int M, std::vector<int> A) {
const int N = A.size();
// create tree with N leefs
vi X, Y;
vi last_level(N, UNASSINED);
int S = 0;
while(last_level.size() != 1)
last_level = create_level(last_level, X, Y, S);
int root = -S;
for(int i = 0; i < S; i++)
if(Y[i]==ROOT)
Y[i] = root;
vi C(M + 1, root);
C[0] = A[0]; // first go to A0, and than everyone goes to root.
vi state(-S);
for(int i = 1; i < N; i++) {
int& v = simulate_untill_next_unassined(root, state, X, Y);
v = A[i];
}
int& last_v = simulate_untill_next_unassined(root, state, X, Y);
last_v = 0;
for(int i : state) assert(i == 0);
for(int i : X) assert(i != UNASSINED);
for(int i : Y) assert(i != UNASSINED);
assert(X.size() == -S);
assert(Y.size() == -S);
answer(C, X, Y);
}