제출 #1274823

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

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int gen(vector<int> &after, vector<int> &X, vector<int> &Y, int &S) {
	int sz = after.size();
	if (sz == 0) {
		return 0;
	}
	if (sz == 1) {
		return after[0];
	}
	else {
		int b = 0;
		while ((1<<b) < sz) {
			b++;
		}
		int pw = (1<<b);
		vector<int> bits(pw), go(pw);
		for (int i=0; i<pw; i++) {
			bits[i] = (bits[i/2])/2 | ((i&1) << (b-1));
		}

		int id = --S;
		for (int i=0; i<b-1; i++) {
			for (int j=0; j<(1<<i); j++) {
				if ((j << (b-i)) + (1 << (b-i)) <= (pw-sz)) {
					;
				}
				else if ((j << (b-i)) + (1 << (b-i-1)) <= (pw-sz)) {
					X.push_back(id);
					Y.push_back(--S);
				}
				else {
					X.push_back(--S);
					Y.push_back(--S);
				}
			}
		}
		int j=0;
		for (int i=0; i<pw; i++) {
			if (bits[i] < (pw-sz)) {
				;
			}
			else {
				go[bits[i]] = after[j++];
			}
		}
		for (int i=0; i<pw/2; i++) {
			if (2*i + 2 <= (pw-sz)) {
				;
			}
			else if (2*i+1 <= (pw-sz)) {
				X.push_back(id);
				Y.push_back(go[2*i+1]);
			}
			else {
				X.push_back(go[2*i]);
				Y.push_back(go[2*i+1]);
			}
		}
		return id;
	}
}

void create_circuit(int M, std::vector<int> A) {
	A.push_back(0);
	int N = A.size();
	vector<int> C(M+1);
	vector<int> X, Y;
	int S=0;
	for (int i=0; i<N; i++) {
		;
	}
	int id = gen(A, X, Y, S);
	for (int i=0; i<M+1; i++) {
		C[i] = id;
	}
	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