Submission #526342

#	Time	Username	Problem	Language	Result	Execution time	Memory
526342		lkh3happy	Mechanical Doll (IOI18_doll)	C++17	0 / 100	1 ms	204 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int idx[800001], dir[800001], cnt, a=1e9;
vector<int> c, x, y;

void create_circuit(int m, vector<int> A){
    c.push_back(A[0]);
    for(int i=1;i<=m;i++) c.push_back(-1);
    A.push_back(0);
    int n=A.size(), k=1;
    while(k<n) k*=2;
    for(int i=k+n;i<k+k;i++) idx[i]=-1;
    for(int i=k-1;i>0;i--) if(idx[i*2]==-1 && idx[i*2+1]==-1) idx[i]=-1;
    for(int i=1;i<=n;i++, a=1e9){
        while(a>=k+n) for(a=1;a<k;dir[a]^=1, a=a*2+(dir[a]^1));
        idx[a]=A[i];
    }
    for(int i=1;i<k;i++) if(!idx[i]) idx[i]=--cnt;
    x.resize(-cnt); y.resize(-cnt);
    for(int i=1;i<k;i++) if(i==1 || idx[i]!=-1) x[-idx[i]-1]=idx[i*2], y[-idx[i]-1]=idx[i*2+1];
    answer(c, x, y);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56