제출 #361603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361603		qwerasdfzxcl	자동 인형 (IOI18_doll)	C++14	84 / 100	128 ms	9644 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int n, mx, d;
int cur=-1;
vector<int> c, x, y;
vector<int> a;
bool cury[500500];

void build2(int val){
    if (val==2){
        x[-cur]=1e9;
        y[-cur]=1e9;
        cur--;
        return;
    }
    int vpos=-cur;
    cur--;
    x[vpos]=cur;
    val >>= 1;
    build2(val);
    y[vpos]=cur;
    build2(val);
}

void build1(int val){
    //printf("%d\n", val);
    if (val==2){
        x[-cur]=1e9;
        if (d&1) y[-cur]=-1;
        else y[-cur]=1e9;
        cur--;
        return;
    }
    int vpos=-cur;
    cur--;
    x[vpos]=cur;
    val >>= 1;
    build1(val);
    if (val&d) y[vpos]=-1;
    else{
        y[vpos]=cur;
        build2(val);
    }
}

void check(){
    c[0]=a[0];
    int pos=a[0], idx=1, prev;
    while(pos){
        //printf("%d\n", pos);
        prev=pos;
        if (pos<0){
            if (!cury[-pos]){
                if (x[-pos]==1e9){
                    x[-pos]=a[idx];
                    pos=a[idx++];
                }
                else pos=x[-pos];
                cury[-prev]=!(cury[-prev]);
            }
            else{
                if (y[-pos]==1e9){
                    y[-pos]=a[idx];
                    pos=a[idx++];
                }
                else pos=y[-pos];
                cury[-prev]=!(cury[-prev]);
            }
        }
        else pos=-1;
    }
}

void create_circuit(int M, vector<int> A){
    n=A.size();
    a.resize(n+1, 0);
    for (int i=0;i<n;i++) a[i]=A[i];
    a[n]=0;
    for (int i=1<<30;i>0;i>>=1){
        if (i&n){
            mx=i<<1; break;
        }
    }
    if (__builtin_popcount(n)==1) mx >>= 1;
    d=mx-n;
    c.resize(M+1, 0);
    x.resize(n+10000, 1e9);
    y.resize(n+10000, 1e9);
    build1(mx);
    //printf("%d\n", x[4]);
    for (int i=1;i<=M;i++) c[i]=-1;
    check();
    int i;
    for (i=n+99;i>=0;i--){
        if (x[i]!=1e9) break;
    }
    vector<int> Rx(i), Ry(i);
    for (int k=0;k<i;k++){
        Rx[k]=x[k+1];
        Ry[k]=y[k+1];
    }
    answer(c, Rx, Ry);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56