제출 #1147198

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

doll

#include "doll.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;

vector<int> a;
vector<int> b;
vector<int> X;
vector<int> Y;
int N;
int rest=0;

struct node {
    node* left;
    node* right;
    int id;
};

int cid=-1;
node *root=new node{NULL,NULL,0};
void build(node* x, int l, int r){
    if(r==l){
        x->id=b[l];
        return;
    }
    x->id=cid--;
    int mid=(l+r)/2;
    x->right=new node{NULL,NULL,0};
    if(mid<rest) {
        x->left=root;
    }
    else {
        x->left=new node{NULL,NULL,0};
        build(x->left,l,mid);
    }
    build(x->right,mid+1,r);
    X[-(x->id)-1]=x->left->id;
    Y[-(x->id)-1]=x->right->id;
}

const int LOG=16;

void create_circuit(int M, std::vector<int> A){
    a=A;
    a.push_back(0);
    vector<int> c(M+1);

    for (int i = 0; i <= M; i++) c[i]=-1;
    int lg2=log2(sz(a)+sz(a)-1);
    int flN=(1<<(lg2));
    b.resize(flN);
    X.resize(sz(a)*2);
    Y.resize(sz(a)*2);
    int k=0;
    rest=flN-sz(a);
    for (int i = 0; i < flN; i++)
    {
        int d=0;
        int cflN=flN/2;
        int j=0;
        while(cflN>0){
            if(i&(1<<j)){
                d+=cflN;
            }
            cflN/=2;
            j++;
        }        
        if(d>=rest){
            b[d]=a[k];
            k++;   
        }else{
            b[d]=-1;   
        }
    }
    build(root, 0, flN-1);
    int S=(-cid)-1;
    X.resize(S);
    Y.resize(S);
    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