Submission #1020113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020113		shenfe1	Mechanical Doll (IOI18_doll)	C++17	100 / 100	72 ms	15388 KiB

doll

#include <bits/stdc++.h>

#include "doll.h"

#define ll long long
#define pb push_back
#define sz(s) (int)s.size()

using namespace std;

const int MAX=2e5+10;

int cnt;
int t[4*MAX];
bool state[4*MAX];

int get(int v,int tl,int tr){
    if(tl==tr)return tl;
    int tm=(tl+tr)/2;
    state[v]^=1;
    if(state[v])return get(2*v,tl,tm);
    else return get(2*v+1,tm+1,tr);
}

int x[MAX],y[MAX];

void build(int v,int tl,int tr,vector<int> &a){
    if(tl==tr){
        if(a[tl]==-1){
            t[v]=MAX;
        }
        else t[v]=a[tl];
        return;
    }
    int tm=(tl+tr)/2;
    build(2*v,tl,tm,a);
    build(2*v+1,tm+1,tr,a);
    if(t[2*v]==MAX&&t[2*v+1]==MAX){
        t[v]=MAX;
        return;
    }
    t[v]=--cnt;
    // cout<<t[v]<<" "<<tl<<" "<<tr<<"\n";
    if(t[2*v]!=MAX){
        x[-t[v]]=t[2*v];
    }
    else{
        x[-t[v]]=MAX;
    }
    if(t[2*v+1]!=MAX){
        y[-t[v]]=t[2*v+1];
    }
    else{
        y[-t[v]]=MAX;
    }
}

void create_circuit(int M, vector<int> A){
    A.pb(0);
    int n=sz(A);
    int cur=1;
    while(cur<sz(A))cur*=2;
    vector<int> f(cur+1,-1);
    vector<int> ord;
    for(int i=0;i<cur;i++){
        int pos=get(1,1,cur);
        if(pos>=cur-n+1){
            ord.pb(pos);
        }
        // cout<<pos<<" ";
    }
    // cout<<'\n';
    for(int i=0;i<n;i++){
        f[ord[i]]=A[i];
    }
    build(1,1,cur,f);
    vector<int> a;
    for(int i=0;i<=M;i++)a.pb(t[1]);
    vector<int> b,c;
    for(int i=1;i<=-cnt;i++){
        if(x[i]==MAX)b.pb(t[1]);
        else b.pb(x[i]);
        if(y[i]==MAX)c.pb(t[1]);
        else c.pb(y[i]);
        // cout<<-i<<" "<<b[i-1]<<"\n"<<-i<<" "<<c[i-1]<<'\n';
    }
    // cout<<-cnt<<"\n";
    // for(int f:b)cout<<f<<" ";
    // cout<<"\n";
    // for(int f:c)cout<<f<<" ";
    // cout<<"\n";
    answer(a,b,c);
}

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