제출 #587081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587081		Josia	자동 인형 (IOI18_doll)	C++14	100 / 100	131 ms	15512 KiB

doll

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

using namespace std;


vector<int> x;
vector<int> y;
void createTree (int v, int n, int next, int &count) {
    if (n > next/2) {
        if (next == 2) {
            x[v] = -2;
            y[v] = -2;
            return;
        }
        x[v] = count+1;
        y[v] = count+2;
        count += 2;

        createTree(x[v], next/2, next/2, count);
        createTree(y[v], n-(next/2), next/2, count);
    }
    else {
        if (next == 2) {
            x[v] = -2;
            y[v] = 0;
            return;
        }
        x[v] = count+1;
        y[v] = 0;
        count += 1;

        createTree(x[v], n, next/2, count);
    }
}





void create_circuit(int M, vector<int> A) {
    int N = A.size();



    if (N == 1) {
        vector<int> ans(M+1);
        ans[0] = A[0];
        answer(ans, {}, {});
        return;
    }


    x.assign(2*N, -1);
    y.assign(2*N, -1);
    // x.push_back(-1);
    // y.push_back(-1);


    int next = 1;
    while (next < N) {
        next *= 2;
    }

    // cerr << next << "\n";

    int count = 0;
    createTree(0, N, next, count);

    swap(x, y);

    // cerr << count << "\n";
    // for (int i = 0; i<N*2; i++) {
    //     cerr << x[i] << " " << y[i] << "\n";
    // }

    vector<int> c(M+1);

    c[0] = A[0];

    for (int i=1; i<=M; i++) c[i] = -1;


    vector<bool> swi(2*N, 0);

    A.push_back(0);

    vector<int> finalX, finalY;

    for (int i = 0; i<2*N; i++) {
        finalX.push_back(-(x[i]+1));
        finalY.push_back(-(y[i]+1));
    }


    // cerr << "\n";

    // for (int i=0; i<2*N; i++) {
    //     cerr << finalX[i] << " " << finalY[i] << "\n";
    // }

    for (int i=1; i<=N; i++) {
        int v = 0;
        while (true) {
            int now;
            if(swi[v]) now = y[v];
            else now = x[v];

            if (now == -2) {
                if(swi[v]) finalY[v] = A[i];
                else finalX[v] = A[i];
                swi[v] = !swi[v];
                break;
            }
            swi[v] = !swi[v];
            v = now;
        }
    }

    // cerr << "\n";

    // for (int i=0; i<2*N; i++) {
    //     cerr << finalX[i] << " " << finalY[i] << "\n";
    // }


    vector<int> resX(count+1);
    vector<int> resY(count+1);

    for (int i=0; i<=count; i++) {
        resX[i] = finalX[i];
        resY[i] = finalY[i];
    }

    answer(c, resX, resY);

}

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