Submission #1229349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229349		LeonidCuk	Mechanical Doll (IOI18_doll)	C++20	100 / 100	63 ms	12188 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-l==1)
    {
        if(l<x)
        {
            st[i].x=0;
        }
        return;
    }
    int m=(l+r)/2;
    if(m<x)st[i].x=0;
    else
    {
        st.push_back(temp);
        st[i].x=timer;timer++;
        naprajst(l,m,st[i].x,x);
    }
    st.push_back(temp);
    st[i].y=timer;timer++;
    naprajst(m+1,r,st[i].y,x);
}
void create_circuit(int M,vector<int>v)
{
    m=M;n=v.size();
    int k=2;
    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: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56