| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 238098 | Jatana | 자동 인형 (IOI18_doll) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <iostream>
#include <algorithm>
#define le(v) ((int)v.size())
#define pb push_back
using namespace std;
vector<int> X, Y;
int inc = 0;
int go(int outs) {
int id = le(X);
X.pb(-1e9); Y.pb(-1e9);
if (outs > 2) {
if (outs & 1) {
outs++;
inc++;
}
X[id] = go(outs / 2);
Y[id] = go(outs / 2);
} else assert(outs == 2);
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]);
inc = 0;
C[i] = go(sz);
wait[i] = inc;
}
}
reverse(after[i].begin(), after[i].end());
}
// for (int x : wait) {
// cout << x << " ";
// }
// return;
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);
}