제출 #118308

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

doll

#include <bits/stdc++.h>

using namespace std;

void answer(vector<int> C, vector<int> X, vector<int> Y);

vector<int> C, X, Y;

const int N = 1e6 + 7;

int B[N][2], timer[N], cnt, n, m, k = 0;

int f(int s, int e){
	if(n <= s){
		return 1;
	}
	if(s == e){
		return -1;
	}

	int m = (s + e) / 2, c = ++k;

	B[c][1] = f(s, m);
	B[c][0] = f(m + 1, e);

	return c;
}

void create_circuit(int M, vector<int> A){
	for(int i = 0; i < M; i++){
		C.push_back(-1);
	}
	C.push_back(-1);

	A.push_back(0);

	n = (int)A.size();
	m = M;

	int t = 1;
	while(t < n){
		t *= 2;
	}

	f(0, t - 1);

	for(int i = 1, c = 0; c < n;){
		int &x = B[i][timer[i] & 1];
		++timer[i];

		if(x < 0){
			x = -A[c++];
			i = 1;
			continue;
		}

		i = x;
	}

	for(int i = 1; i <= k; i++){
		X.push_back(-B[i][0]);
		Y.push_back(-B[i][1]);
	}

	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