제출 #612104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612104		krit3379	자동 인형 (IOI18_doll)	C++17	53 / 100	304 ms	51024 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];
bitset<N> ch,out;
vector<int> c,x,y,pos[N];
map<int,int> mp,id;

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){
            ch[s]=true;
            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 upd(int s,int st,int f,vector<int> &a){
    if(ch[s]){
        if(l[s]==st&&r[s]==st)l[s]=r[s]=f;
        return ;
    }
    upd(l[s],st,s,a);
    upd(r[s],st,s,a);
    if(l[l[s]]==f&&r[l[s]]==f&&l[r[s]]==f&&r[r[s]]==f){
        out[l[s]]=true;
        l[s]=f;
        out[r[s]]=true;
        r[s]=f;
    }
}

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);
            upd(-c[x],-c[x],x,a);
        }
    }
    now=0;
    for(i=1;i<=sz;i++)if(!out[i])id[i]=--now;
    for(auto &x:c)if(x<0)x=id[-x];
    for(i=1;i<=sz;i++){
        if(l[i]>0)x.push_back(id[l[i]]);
        else x.push_back(-l[i]);
        if(r[i]>0)y.push_back(id[r[i]]);
        else 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