제출 #1368732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368732		mariza	자동 인형 (IOI18_doll)	C++20	10 / 100	1 ms	344 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> s0, s1;

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

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

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

        if((1ll<<i)&n){
            s0.push_back(-(s+1));
            for(ll j=1; j<(1ll<<i)/2; j++){
                s0.push_back(-(s+2*j));
                s1.push_back(-(s+2*j+1));
            }
            for(ll j=(1ll<<i)/2; j<(1ll<<i); j++){
                s0.push_back(INF);
                s1.push_back(INF);
            }
        }
        else{
            s0.push_back(-1);
        }
    }

    // // JUST FOR TESTING
    // vector<int> c(m+1,-1);
    // answer(c,s0,s1);
    // return;

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


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

    vector<int> c(m+1,-1);
    answer(c,s0,s1);
}

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