Submission #611994

#	Time	Username	Problem	Language	Result	Execution time	Memory
611994		krit3379	Mechanical Doll (IOI18_doll)	C++17	53 / 100	203 ms	32308 KiB

doll

#include<bits/stdc++.h>
#include "doll.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 500005

int l[N],r[N],sz,now;
bool sw[N];
vector<int> c,x,y,pos[N];
map<int,int> mp;

int bi(int x){
    int i=1;
    while(i<x)i<<=1;
    return i;
}

int bic(int x){
    int i=1,cnt=0;
    while(i<x)i<<=1,cnt++;
    return cnt;
}

int cre(int lev){
    int s=++sz;
    if(lev==1){
        l[s]=-1;
        r[s]=-1;
        return s;
    }
    l[s]=(cre(lev-1));
    r[s]=(cre(lev-1));
    return s;
}

void dfs(int s,int st,int head,vector<int> &a){
    if(now<=0)return ;
    if(!sw[s]){
        sw[s]^=1;
        if(l[s]==-1){
            int ps=pos[head].size();
            if(now<=ps)l[s]=-a[pos[head][ps-now]+1];
            else l[s]=st;
            now--;
            dfs(st,st,head,a);
        }
        else dfs(l[s],st,head,a);
    }
    else{
        sw[s]^=1;
        if(r[s]==-1){
            int ps=pos[head].size();
            if(now<=ps)r[s]=-a[pos[head][ps-now]+1];
            else r[s]=st;
            now--;
            dfs(st,st,head,a);
        }
        else dfs(r[s],st,head,a);
    }
}

void create_circuit(int m,vector<int> a){
    int i;
    c.resize(m+1);
    c[0]=a[0];
    i=0;
    for(auto x:a){
        mp[x]++;
        pos[x].push_back(i);
        i++;
    }
    a.push_back(0);
    for(auto [x,y]:mp){
        if(mp[x]==1)c[x]=a[pos[x][0]+1];
        else{
            now=bi(y);
            c[x]=-cre(bic(y));
            dfs(-c[x],-c[x],x,a);
        }
    }
    for(i=1;i<=sz;i++)x.push_back(-l[i]),y.push_back(-r[i]);
    answer(c,x,y);
}

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