제출 #465000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465000		blue	자동 인형 (IOI18_doll)	C++17	100 / 100	266 ms	11752 KiB

doll

#include "doll.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int N;
int k;

const int rt = 1e9;

vector<int> I;

void create_circuit(int M, vector<int> A)
{
    N = A.size();
    // if(A.size() == 1)
    // {
    //     vector<int> C(M+1, 0);
    //     C[0] = A[0];
    //     vector<int> X(0), Y(0);
    //     answer(C, X, Y);
    //     return;
    // }

    for(k = 0; (1 << k) < N; k++);

    I = vector<int>( (1 << k) );
    for(int i = 0; i < (1 << k); i++)
        I[i] = i;

    sort(I.begin(), I.end(), [] (int p, int q)
    {
        for(int y = 0; y < k; y++)
        {
            if((p & (1 << y)) < (q & (1 << y)))
                return 1;
            else if((q & (1 << y)) < (p & (1 << y)))
                return 0;
        }
        return 0;
    });

    vector<int> J(N);
    for(int i = 0; i < N; i++) J[i] = I.size() - N + i;
    sort(J.begin(), J.end(), [] (int x, int y)
    {
        return I[x] < I[y];
    });

    vector<int> A1[k+1];

    A1[k] = vector<int>((1 << k), rt);

    for(int i = 1; i < N; i++)
        A1[k][ J[i-1] ] = A[i];

    A1[k][J[N-1]] = 0;


    int S = 0;
    vector<int> C(M+1);
    vector<int> X;
    vector<int> Y;
    for(int l = k-1; l >= 0; l--)
    {
        for(int i = 0; i < (1 << l); i++)
        {
            if(A1[l+1][2*i] == A1[l+1][2*i+1])
                A1[l].push_back(A1[l+1][2*i]);
            else
            {
                S++;
                A1[l].push_back(-S);
                X.push_back(A1[l+1][2*i]);
                Y.push_back(A1[l+1][2*i+1]);
            }
        }
    }
    C[0] = A[0];
    for(int i = 1; i <= M; i++)
        C[i] = -S;

    for(int j = 1; j <= S; j++)
    {
        if(X[j-1] == rt)
            X[j-1] = -S;
        if(Y[j-1] == rt)
            Y[j-1] = -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