Submission #1123209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123209		mnbvcxz123	Mechanical Doll (IOI18_doll)	C++20	0 / 100	1093 ms	6320 KiB

doll

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

#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()

constexpr int INF=1e9;

vector<int>x,y,state,hm;

int p=1,p2=0;

void give_ind(int k, int l, int r){
        int mid=(l+r)>>1;
        if(r-l==1){
                if(mid+1>sz(hm))x[k]=-1;
                return;
        }
        if(mid+1>sz(hm))x[k]=-1;
        else{
                x[k]=-(++p);
                x.push_back(-INF);
                y.push_back(-INF);
                state.push_back(0);
                give_ind(-x[k],mid+1,r);
        }
        y[k]=-(++p);
        x.push_back(-INF);
        y.push_back(-INF);
        state.push_back(0);
        give_ind(-y[k],l,mid);
}

void make_leaf(int k){
        if(!state[k]){
                state[k]^=1;
                if(x[k]==-INF)x[k]=hm[p2++];
                else make_leaf(-x[k]);
        }else{
                state[k]^=1;
                if(y[k]==-INF)y[k]=hm[p2++];
                else make_leaf(-y[k]);
        }
}

void create_circuit(int m, vector<int>a){
        int n=a.size();

        vector<int>c(m+1);
        x.push_back(-INF);
        y.push_back(-INF);
        state.push_back(0);
        a.push_back(0);
        x.push_back(-INF);
        y.push_back(-INF);
        state.push_back(0);

        for(int i=0;i<=m;++i)c[i]=-1;

        hm=a;
        int p=1;
        while(p<m+1)p<<=1;
        give_ind(1,1,p);
        for(int i=0;i<sz(hm);++i)
                make_leaf(1);
        reverse(all(x));
        x.pop_back();
        reverse(all(x));
        reverse(all(y));
        y.pop_back();
        reverse(all(y));
        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