제출 #1189713

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

doll

#include "doll.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

void ans();

int C[400'001];
int X[400'001];
int Y[400'001];
bool T[400'001];
int S = 1;
int n,lg,m;

void gen_tree(int v, int elm, int level, int end_level)
{
    if(level == end_level)
    {
        if(!T[-v])
        {
            X[-v] = elm;
            T[-v] = 1;
        }
        else
        {
            T[-v] = 0;
            Y[-v] = elm;
        }
        return;
    }
    if(!T[-v])
    {
        T[-v] = 1;
        if(X[-v] == -1) X[-v] = -(S++);
        gen_tree(X[-v],elm,level+1,end_level); 
    }
    else
    {
        T[-v] = 0;
        if(Y[-v] == -1) Y[-v] = -(S++);
        gen_tree(Y[-v],elm,level+1,end_level);
    }
}

void create_circuit(int M, vi A) 
{
    m = M;
    n = siz(A);
    lg = __lg(n);
    C[0] = -1;
    rep2(i,1,m)
    {
        C[i] = -1;
    }
    rep2(i,1,400'000) X[i] = -1;
    rep2(i,1,400'000) Y[i] = -1;
    rep2(i,1,lg+1)
    {
        Y[i] = -(i+1);
        S++;
        if(i == lg+1)
        {
            Y[i] = 0;
        }
    } 
    int cur_elm = 0;
    int cur_vert = -1;
    while(cur_vert != 0)
    {
        if(cur_vert >= 0)
        {
            cur_elm++;
            cur_vert = -1;
            continue;
        }
        if(T[-cur_vert])
        {
            T[-cur_vert] = 0;
            cur_vert = Y[-cur_vert];
            continue;  
        }
        T[-cur_vert] = 1;
        if(n & (1 << (lg + cur_vert+1)))
        {
            if((lg + cur_vert+1) == 0)
            {
                X[-cur_vert] = A[cur_elm];
                cur_vert = A[cur_elm];
                continue;
            }
            if(X[-cur_vert] == -1) X[-cur_vert] = -(S++);
            gen_tree(X[-cur_vert],A[cur_elm],1,lg+cur_vert+1);
            cur_vert = A[cur_elm];
        }
        else
        {
            cur_vert = -1;
        }
    }
    ans();
}

void ans()
{
    vi c;
    vi x;
    vi y;
    rep2(i,0,m)
    {
        c.pb(C[i]);
    }
    rep2(i,1,S-1)
    {
        x.pb(X[i]);
        y.pb(Y[i]);
    }
    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