제출 #1368740

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

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF=1e9;

void create_circuit(int m, vector<int> a){
    ll n=a.size();

    vector<int> s[2];

    ll k=0;
    while((1ll<<k)<=n) k++;

    for(ll i=k-1; i>=0; i--){
        ll sn=s[0].size()+1;

        if(i==0) s[1].push_back(0);
        else if((1ll<<i)&n) s[1].push_back(-(sn+(1ll<<i)));
        else s[1].push_back(-(sn+1));

        if((1ll<<i)&n){
            if(i==0){
                s[0].push_back(INF);
                continue;
            }

            s[0].push_back(-(sn+1));
            for(ll j=1; j<(1ll<<i)/2; j++){
                s[0].push_back(-(sn+2*j));
                s[1].push_back(-(sn+2*j+1));
            }
            for(ll j=(1ll<<i)/2; j<(1ll<<i); j++){
                s[0].push_back(INF);
                s[1].push_back(INF);
            }
        }
        else{
            s[0].push_back(-1);
        }
    }

    // JUST FOR TESTING
    // vector<int> c(m+1,-1);
    // answer(c,s[0],s[1]);

    bool x[s[0].size()]={};
    for(ll i=0; i<n; i++){
        // cout<<i<<endl;
        ll curr=-1;
        while(s[x[-curr-1]][-curr-1]!=INF){
            // cout<<curr<<" "<<x[-curr-1]<<" "<<s[x[-curr-1]][-curr-1]<<endl;
            x[-curr-1]=!x[-curr-1];
            // cout<<x[-curr-1]<<endl;
            if(x[-curr-1]==0) curr=s[1][-curr-1];
            else curr=s[0][-curr-1];
            // cout<<curr<<" "<<x[-curr-1]<<endl;
        }

        if(x[-curr-1]==0) s[0][-curr-1]=a[i];
        else s[1][-curr-1]=a[i];
        x[-curr-1]=!x[-curr-1];
    }

    vector<int> c(m+1,-1);
    answer(c,s[0],s[1]);
}

• 서브태스크 1: 2 / 2
• 서브태스크 2: 4 / 4
• 서브태스크 3: 10 / 10
• 서브태스크 4: 10 / 10
• 서브태스크 5: 18 / 18
• 서브태스크 6: 56 / 56