# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
560707 | tfg | 자동 인형 (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
const int MAGIC = 1e9;
std::vector<int> X, Y;
int solve(int sz) {
int id = (int) X.size();
X.push_back(MAGIC), Y.push_back(MAGIC);
if(sz == 1) {
X[id] = -id-1;
} else if(sz > 2) {
X[id] = solve(sz/2);
Y[id] = solve(sz/2);
}
return -id-1;
}
int outerSolve(const std::vector<int> &A) {
int n = (int) A.size();
if(n == 1) {
solve(1);
Y.back() = A.back();
}
int id = 0;
while((1 << id) * 2 <= n) id++;
for(int i = 0; i < id; i++) {
X.push_back(((1 << (id - i)) & n) ? MAGIC : -1), Y.push_back(-(i+1)-1);
}
Y.back() = n % 2 ? MAGIC : -1;
for(int i = 0; i < id; i++) {
if(X[i] == MAGIC) {
X[i] = solve(1 << (id - i));
//std::cout << "tree for 2^" << (id-i) << " in " << X[i] << std::endl;
}
}
std::vector<bool> state(X.size(), false);
for(auto val : A) {
int on = -1;
//std::cout << "val is " << val << std::endl;
while(on < 0) {
//std::cout << "on " << on << std::endl;
assert(on < 0);
state[-on-1] = !state[-on-1];
int &nxt = (state[-on-1] ? X : Y)[-on-1];
if(nxt >= 0) {
assert(nxt == MAGIC);
nxt = val;
}
on = nxt;
}
assert(on == val);
}
return -1;
}
void create_circuit(int M, std::vector<int> A) {
int N = A.size();
std::vector<int> C(M + 1, -1);
C[0] = A[0];
A.erase(A.begin());
A.push_back(0);
outerSolve(A);
answer(C, X, Y);
}