Submission #526301

#	Time	Username	Problem	Language	Result	Execution time	Memory
526301		lkh3happy	Mechanical Doll (IOI18_doll)	C++17	10 / 100	1 ms	300 KiB

doll

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

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

void del(int n, int k){
    if(n>=k) return;
    del(n*2, k); del(n*2+1, k);
    if(idx[n*2]==-1 && idx[n*2+1]==-1) idx[n]=-1;
}

int find(int n, int k){
    if(n>=k) return n;
    if(!dir[n]){
        dir[n]=1;
        return find(n*2, k);
    }
    else{
        dir[n]=0;
        return find(n*2+1, k);
    }
}

void num(int n, int k){
    if(n>=k || idx[n]) return;
    idx[n]=--cnt;
    num(n*2, k); num(n*2+1, k);
}

void ans(int n, int k){
    if(n>=k || (n!=1 && idx[n]==-1)) return;
    x[-idx[n]-1]=idx[n*2]; y[-idx[n]-1]=idx[n*2+1];
    ans(n*2, k); ans(n*2+1, k);
}

void create_circuit(int m, vector<int> A){
    c.push_back(A[0]);
    A.erase(A.begin());
    if(A.empty()){
        for(int i=1;i<=m;i++) c.push_back(0);
        answer(c, x, y);
        return;
    }
    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;
    del(1, k);
    for(int i=0;i<n;i++){
        int a=find(1, k);
        while(a>=k+n) a=find(1, k);
        idx[a]=A[i];
    }
    num(1, k);
    for(int i=1;i<=m;i++) c.push_back(-1);
    x.resize(-cnt); y.resize(-cnt);
    ans(1, k);
    answer(c, x, y);
}

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