| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 440110 | rainboy | Mechanical Doll (IOI18_doll) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "doll.h"
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int M = 100000, N_ = 1 << 18; /* N_ = pow2(ceil(log2(N))) */
int tmp[N_];
void split(int *aa, int n) {
int i, j, k;
for (i = 0, j = n / 2, k = 0; k < n; k++)
tmp[k % 2 == 0 ? i++ : j++] = aa[k];
memcpy(aa, tmp, n * sizeof *tmp);
}
vi xx, yy;
int build(int *aa, int n) {
static int k;
int idx = k++;
if (n == 2)
xx[idx] = aa[0], yy[idx] = aa[1];
else {
split(aa, n);
xx[idx] = -(build(aa, n / 2) + 1), yy[idx] = -(build(aa + n / 2, n / 2) + 1);
}
return idx;
}
int kk[M + 1], aa[N_];
void create_circuit(int m, vi aa_) {
vi cc(m + 1);
int n = aa_.size(), n_, n1, i, j;
for (i = 0; i < n; i++)
kk[aa_[i]]++;
for (j = 0; j <= m; j++)
cc[j] = -1;
cc[0] = aa_[0];
n1 = 0;
for (i = 0; i < n; i++)
if (kk[aa_[i]] > 1)
aa_[n1++] = i == n - 1 ? 0 : aa_[i + 1];
else
cc[aa_[i]] = i == n - 1 ? 0 : aa_[i + 1];
if (n1 != 0) {
n_ = 1;
while (n_ < n1)
n_ <<= 1;
for (i = 0; i < n_ - n1; i++)
aa[i] = -1;
for (i = 0; i < n1; i++)
aa[n_ - n1 + i] = aa_[i];
for (i = 0; i < n_; i++)
printf("%d ", aa[i]);
printf("\n");
xx.resize(n_ - 1), yy.resize(n_ - 1);
build(aa, n_);
} else
for (j = 0; j <= m; j++)
if (cc[j] == -1)
cc[j] = 0;
answer(cc, xx, yy);
}