| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 541158 | MilosMilutinovic | Mechanical Doll (IOI18_doll) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dolls.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int m, vector<int> a) {
int n = a.size();
vector<vector<int>> nxt(m + 1);
for (int i = 0; i + 1 < n; i++) {
nxt[a[i]].push_back(a[i + 1]);
}
nxt[0].push_back(a[0]);
nxt[a.back()].push_back(0);
vector<int> ans(m + 1);
vector<int> x;
vector<int> y;
int idx = 0;
for (int i = 0; i <= m; i++) {
if (nxt[i].empty()) {
ans[i] = 0;
continue;
}
if (nxt[i].size() == 1) {
ans[i] = nxt[i][0];
continue;
}
vector<int> vec = nxt[i];
int pw = 1;
while (pw < (int) vec.size()) pw *= 2;
reverse(vec.begin(), vec.end());
while ((int) vec.size() < pw) vec.push_back(-1);
reverse(vec.begin(), vec.end());
vector<int> order(pw);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
int ni = 0, nj = 0;
for (int b = 0; b < 30; b++) {
if (i >> b & 1) {
ni += (1 << (30 - b));
}
if (j >> b & 1) {
nj += (1 << (30 - b));
}
}
return ni < nj;
});
auto tmp = vec;
for (int i = 0; i < pw; i++) {
vec[i] = tmp[order[i]];
}
vector<int> pref(pw);
for (int i = 0; i < pw; i++) {
if (i > 0) {
pref[i] = pref[i - 1];
}
pref[i] += (vec[i] != -1 ? 1 : 0);
}
auto Get = [&](int L, int R) {
int sum = pref[R];
if (L > 0) {
sum -= pref[L - 1];
}
return sum;
};
--idx;
ans[i] = idx;
vector<pair<int, int>> que;
que.push_back({0, pw - 1});
for (int b = 0; b < (int) que.size(); b++) {
int l = que[b].first;
int r = que[b].second;
if (l + 1 == r) {
x.push_back(vec[l] == -1 ? ans[i] : vec[l]);
y.push_back(vec[r] == -1 ? ans[i] : vec[r]);
continue;
}
int mid = l + r >> 1;
{
if (Get(l, mid) != 0) {
--idx;
x.push_back(idx);
que.push_back({l, mid});
} else {
x.push_back(ans[i]);
}
}
{
if (Get(mid + 1, r) != 0) {
--idx;
y.push_back(idx);
que.push_back({mid + 1, r});
} else {
y.push_back(ans[i]);
}
}
}
}
answer(ans, x, y);
}