제출 #1228742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228742		LeonidCuk	자동 인형 (IOI18_doll)	C++20	68.82 / 100	100 ms	11420 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
struct teme{
    int x=-1,y=-1;
    bool ukl=true;
};
int n,m,timer=1;
vector<teme>st;
teme temp;
void naprajst(int l,int r,int i,int x)
{
    if(r<x)
    {
        st[i].x=i;
        st[i].y=0;
        return;
    }
    if(r-l==1)
    {
        if(l<x)
        {
            st.push_back(temp);
            st[i].x=timer;timer++;
            naprajst(l,l,st[i].x,x);
        }
        return;
    }
    st.push_back(temp);
    st.push_back(temp);
    st[i].x=timer;timer++;
    st[i].y=timer;timer++;
    int m=(l+r)/2;
    naprajst(l,m,st[i].x,x);
    naprajst(m+1,r,st[i].y,x);
}
void create_circuit(int M,vector<int>v)
{
    m=M;n=v.size();
    int k=1;
    while(k<n){k*=2;}
    st.push_back(temp);
    naprajst(0,k-1,0,k-n);
    if(n==1)
    {
        vector<int>c1(M+1),x1,y1;
        c1[0]=v[0];
        c1[v[0]]=0;
        answer(c1,x1,y1);
        return;
    }
    vector<int>c(M+1,-1),x(st.size()),y(st.size());
    for(int i=1;i<n;i++)
    {
        int a=0;
        c[v[i]]=-1;
        while(true)
        {
            if(st[a].ukl)
            {
                st[a].ukl^=1;
                if(st[a].x==-1)
                {
                    st[a].x=-v[i];break;
                }
                a=st[a].x;
            }
            else
            {
                st[a].ukl^=1;
                if(st[a].y==-1)
                {
                    st[a].y=-v[i];break;
                }
                a=st[a].y;
            }
        }
    }
    c[0]=v[0];
    for(int i=0;i<st.size();i++)
    {
        if(st[i].x>=0)x[i]=-(st[i].x+1);
        else x[i]=-st[i].x;
        if(st[i].y>=0)y[i]=-(st[i].y+1);
        else y[i]=-st[i].y;
    }
    y[st.size()-1]=0;
    answer(c,x,y);

}

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