Submission #604833

#	Time	Username	Problem	Language	Result	Execution time	Memory
604833		DanShaders	자동 인형 (IOI18_doll)	C++17	37 / 100	134 ms	14720 KiB

doll

//Dgrader.cpp
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 4e5 + 10;

pair<int, int> switches[N];
int next_free = 1;

int create(vector<int> a) {
	int result = next_free++;
	if (sz(a) == 1) {
		switches[result] = {-result, a[0]};
	} else if (sz(a) == 2) {
		switches[result] = {a[0], a[1]};
	} else {
		vector<int> left, right;
		for (int i = 0; i < sz(a); ++i) {
			(i % 2 ? right : left).push_back(a[i]);
		}
		switches[result] = {
			(count(all(left), -1) == sz(left)) ? -1 : -create(left),
			(count(all(right), -1) == sz(right)) ? -1 : -create(right)
		};
	}
	return result;
}

void create_circuit(int m, vector<int> a) {
	while (1) {
		int total = sz(a) + 1;
		if (!(total & (total - 1))) {
			break;
		}
		a.push_back(-1);
	}
	a.push_back(0);
	create(a);
	vector<int> xs, ys;
	for (int i = 1; i < next_free; ++i) {
		xs.push_back(switches[i].x);
		ys.push_back(switches[i].y);
		// cout << -i << ": " << switches[i].x << " " << switches[i].y << endl;
	}
	answer(vector<int>(m + 1, -1), xs, ys);
}

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