# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1188738 | Ak_16 | Mechanical Doll (IOI18_doll) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include "dolls.h"
using namespace std;
int bad[1000000];
int po[20];
int n;
int inc[1000000];
int l[1000000];
int r[1000000];
int par[1000000];
int swi[1000000];
int swipos[1000000];
int tri[1000000];
int tripos[1000000];
int lf;
int scnt;
int tcnt;
vector<int> c;
vector<int> x;
vector<int> y;
int nx;
void rem(int num){
bad[num]=1;
if(inc[num]==0){return;}
int n1 = num + inc[num];
int n2 = num + 2*inc[num];
rem(n1);
rem(n2);
}
void create_circuit(int m, vector<int> a){
for(int i=0; i<1e6; i++){
bad[i]=0;
}
n = a.size();
int anew[1000000];
for(int i=0; i<n; i++){
anew[i]=a[i];
}
anew[n]=0;
po[0]=1;
for(int i=1; i<=19; i++){
po[i] = 2*po[i-1];
}
c.push_back(a[0]);
for(int i=1; i<=m; i++){
c.push_back(-1);
}
for(int i=0; i<=20; i++){
if(po[i]>=n){
nx=i; break;
}
}
for(int i=0; i<nx; i++){
for(int j=po[i]; j<po[i+1]; j++){
l[j] = j+po[i];
r[j] = j+po[i+1];
par[j+po[i]] = j;
par[j+po[i+1]] = j;
inc[j] = po[i];
}
}
for(int i=po[nx]; i<po[nx+1]; i++){
inc[i]=0;
}
lf=po[nx]-n;
int bi[30];
for(int i=19; i>=0; i--){
if(lf>=po[i]){
bi[i]=1;
lf -= po[i];
}
else {
bi[i]=0;
}
}
for(int i=0; i<=nx; i++){
if(bi[nx-i]==1){
int imp;
for(int j=po[i]; j<po[i+1]; j++){
if(bad[j]==0){
imp=j; break;
}
}
rem(imp);
}
}
scnt=0;
tcnt=0;
for(int i=po[nx]; i<po[nx+1]; i++){
if(bad[i]==0){
tcnt++;
tri[tcnt]=i;
tripos[i]=tcnt;
}
}
for(int i=1; i<po[nx]; i++){
if(bad[i]==0){
scnt++;
swi[scnt]=i;
swipos[i]=scnt;
}
}
for(int i=1; i<=scnt; i++){
int k = swi[i];
if(bad[l[k]]==1){
x.push_back(-1);
}
else if(inc[l[k]]==0){
x.push_back(anew[tripos[l[k]]]);
}
else {
x.push_back(-swipos[l[k]]);
}
if(bad[r[k]]==1){
y.push_back(-1);
}
else if(inc[r[k]]==0){
y.push_back(anew[tripos[r[k]]]);
}
else {
y.push_back(-swipos[r[k]]);
}
}
answer(c, x, y);
}