| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 415681 | LastRonin | 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.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "doll.h"
#define ll long long
#define pill pair<ll, ll>
#define ex exit(0)
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
const ll N = 8e5 + 100;
ll n;
vector<int> g[N];
ll cur = 0;
ll L[N], R[N];
bool leave[N];
bool sost[N];
void build(int v, int l, int r) {
if(l == r) {
leave[v] = 1;
return;
}
ll m = (l + r) >> 1ll;
if(l != m)
L[v] = cur++, build(L[v], l, m);
if(m + 1 != r)
R[v] = cur++, build(R[v], m + 1, r);
}
void spusk(int v, int p, int l, int r) {
int m = (l + r) >> 1ll;
if(sost[v] == 0) {
sost[v] = 1;
if(l == m) {
L[v] = p;
return;
}
else {
spusk(L[v], p, l, m);
}
}
else {
sost[v] = 0;
if(m + 1== r) {
R[v] = p;
return;
}
else {
spusk(R[v], p, m + 1, r);
}
}
}
void create_circuit(int m, vector<int> a) {
n = a.size();
vector<int> C(m + 1), X, Y;
C[0] = -1;
for(int i = 1; i <= m; i++)C[i] = -1;
ll z = __lg(n) + 1;
build(0, 1, (1<<z));
ll dl = (1<<z) - (n + 1);
while(dl--)spusk(0, -1);
for(int i = 0; i < n; i++) {
spusk(0, a[i]);
}
spusk(0, 0);
for(int i = 0; i < cur; i++) {
if(leave[i]) {
X.pb(L[i]), X.pb(R[i]);
}
else {
X.pb(-(L[i] + 1)), Y.pb(-(R[i] + 1));
}
}
/* for(auto u : C)
cout << u << " ";
cout << '\n';
for(int i = 0; i < cur; i++)
cout << X[i] << " " << Y[i] << '\n'; */
answer(C, X, Y);
}
/*
int main() {
ll k, kk;
cin >> k >> kk;
vector<int> p;
for(int i = 0, a; i < kk; i++)
cin >> a, p.pb(a);
create_circuit(k, p);
}
*/