제출 #1278348

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

doll

#include<iostream>
#include<vector>
#include<cmath>
#include "doll.h"
using namespace std;
vector<int>x,y,c,state,a;
int NN;
int nodes;

void new_node()
{
    nodes++;
    x.push_back(0);y.push_back(0);state.push_back(0);
}
void power2(int bit,int cur)
{
    if(bit>1)
    {
        new_node();
        x[cur-1]=-nodes;
        power2(bit-1,nodes);
        new_node();
        y[cur-1]=-nodes;
        power2(bit-1,nodes);
    }
    else
    {
        x[cur-1]=0;y[cur-1]=0;
    }
}

void create(int n,int bit,int par)
{
    new_node();
    int cur=nodes;
    if(par!=0)
    {
        y[par-1]=-cur;
    }
    if(bit==0)
    {
        if(n%2==1)x[cur-1]=0;
        else x[cur-1]=-1;

        y[cur-1]=0;///should be the last
        return;
    }
    if(((1<<bit)&(n))!=0)
    {
        new_node();
        x[cur-1]=-nodes;
        power2(bit,nodes);
    }
    else
    {
        x[cur-1]=-1;
    }
    create(n,bit-1,cur);
}

int idx;
int curnode;
int statesX;
void run()
{
    while(1)
    {
        int id=(-curnode)-1;
        int nxtnode;
        if(state[id]==0)
        {
            nxtnode=x[id];
            state[id]=1;
            statesX--;
        }
        else
        {
            nxtnode=y[id];
            state[id]=0;
            statesX++;
        }
        if(nxtnode==-1)break;
        if(nxtnode==0)
        {
            if(state[id]==1)
            {
                x[id]=a[idx];
            }
            else
            {
                y[id]=a[idx];
            }
            idx++;
            break;
        }
        curnode=nxtnode;
    }
}

void simu()
{
    a.push_back(0);
    idx=0;
    statesX=nodes;
    do
    {
        curnode=-1;
        run();

    }while(statesX!=nodes);
}

void create_circuit(int M, std::vector<int> A)
{
    a=A;
    NN=a.size();
    c.resize(M+1);
    for(int i=0;i<=M;i++)c[i]=-1;

    int bb;
    for(int bit=20;bit>=0;bit--)
    {
        if((1<<bit)<=NN)
        {
            bb=bit;
            break;
        }
    }

    create(NN,bb,0);
    simu();

    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