Submission #526360

#	Time	Username	Problem	Language	Result	Execution time	Memory
526360		lkh3happy	Mechanical Doll (IOI18_doll)	C++17	100 / 100	108 ms	14596 KiB

doll

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

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

void create_circuit(int m, vector<int> A){
    c.push_back(A[0]);
    int n=A.size(), k=1;
    A.push_back(0);
    for(int i=1;i<=m;i++) c.push_back(-1+(n==1));
    while(k<n) k*=2;
    for(int i=k;i<k+k-n;i++) idx[i]=-1;
    for(int i=k-1;i>0;i--) idx[i]=(idx[i*2]+idx[i*2+1])/2;
    for(int i=1;i<=n;i++, a=0){
        while(a<k-n+k) 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: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56