| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 595128 | TimDee | 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 "doll.h"/*
*/
#include <bits/stdc++.h>
using namespace std;
struct tree {
int n, size;
vector<int> t, x, y, state;
void build(int N, int amt) {
n=N;
size=1;
while ((size<<1)<n) size<<=1;
t.assign(2*size-1,0), x.assign(2*size-1,0), y.assign(2*size-1,0), state.assign(2*size-1,0);
for (int i=1; i<=size-1; ++i) {
x[i-1] = -(2*i);
y[i-1] = -(2*i+1);
}
int cnt=0, p=0;
while (cnt<2*size-amt) {
if (p>=size-1) {
if (state[p]) {
y[p]=-1;
} else {
x[p]=-1;
}
state[p]^=1;
++cnt;
p=0;
continue;
}
if (!state[p]) {
state[p]^=1;
p<<=1; ++p;
} else {
state[p]^=1;
++p; p<<=1;
}
}
}
};
void create_circuit(int m, vector<int>a) {
int n=a.size();
vector<int> cnt(m+1,0);
int mx=0;
for (int i=0; i<n; ++i) {
cnt[a[i]]++;
mx=max(mx,cnt[a[i]]);
}
if (mx==1) {
vector<int> c(m+1,0);
c[0]=a[0];
for (int i=1; i<n; ++i) {
c[a[i-1]]=a[i];
}
vector<int> x(0), y(0);
answer(c,x,y);
} else if (mx==2) {
vector<vector<int>> next(m+1);
//vector<int> b=a;
a.push_back(0);
for (int i=0; i<n; ++i) next[a[i]].push_back(a[i+1]);
vector<int> c(m+1);
c[0]=a[0];
for (int i=1; i<=m; ++i) {
c[i]=-i;
}
vector<int> x(m,0), y(m,0);
for (int i=1; i<=m; ++i) {
if (!next[i].size()) continue;
x[i-1] = next[i].size()>1 ? next[i][0] : -(i);
y[i-1] = next[i].size()>1 ? next[i][1] : next[i][0];
}
//if (cnt[a[n-1]]==2) {
//
//} else {
//
//}
answer(c,x,y);
} else if (n==16) {
vector<int> c(m+1,-1); c[0]=a[0];
vector<int> x(15), y(15);
for (int i=0;i<7;++i) {x[i]=-(2*i+2); y[i]=-(2*i+3);}
x[7]=a[1], x[11]=a[2], x[9]=a[3], x[13]=a[4], x[8]=a[5], x[12]=a[6], x[10]=a[7], x[14]=a[8];
Y[7]=a[9], y[11]=a[10], y[9]=a[11], y[13]=a[12], y[8]=a[13], y[12]=a[14], y[10]=a[15], y[14]=0;
answer(c,x,y);
} else if (m==1) {
int size=1;
while (4*size<n) size<<=1;
vector<int> x(2*size+1), y(2*size+1), state(2*size+1,0), c = {1, -(2*size)};
for (int i=1; i<=size-1; ++i) {
x[i-1] = -(2*i);
y[i-1] = -(2*i+1);
}
x[2*size-1]=-(2*size+1);
y[2*size-1]=-1;
x[2*size] = y[2*size] = 1;
int cnt=0, p=0;
while (cnt<2*size) {
//cout<<p<<"->";
if (p>=size-1) {
//cout<<"added "<<p<<' '<<cnt<<'\n';
if (state[p]) {
if (cnt<n-1-2*size) y[p]=1;
else y[p]=-(2*size);
} else {
if (cnt<n-1-2*size) x[p]=1;
else x[p]=-(2*size);
}
state[p]^=1;
++cnt;
p=0;
continue;
}
if (!state[p]) {
state[p]^=1;
p<<=1; ++p;
} else {
state[p]^=1;
++p; p<<=1;
}
}
y[2*size-2]=0;
answer(c,x,y);
} else {
vector<int> c(m+1),x,y;
c[0]=a[0];
vector<tree> v(m+1);
for (int i=1; i<=m; ++i) v[i].build(cnt[i],cnt[i]);
int in=0, p=0;
while (in<n) {
int ind = a[in];
while (p<v[ind].size-1) {
if (!v[ind].state[p]) {
v[ind].state[p]^=1;
p<<=1;
++p;
} else {
v[ind].state[p]^=1;
++p;
p<<=1;
}
}
if (!v[ind].state[p]) {
v[ind].x[p]= ((++in)<n) ? a[in] : 0;
v[ind].state[p]^=1;
} else {
v[ind].y[p]= ((++in)<n) ? a[in] : 0;
v[ind].state[p]^=1;
}
p=0;
}
for(int i=1; i<=m; ++i) {
int sz=x.size();
for (auto X:v[i].x) x.push_back( X>=0 ? X : (X-sz) );
for (auto Y:v[i].y) y.push_back( Y>=0 ? Y : (Y-sz) );
c[i]=-1-sz;
}
answer(c,x,y);
}
}