Submission #1197863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197863		MateiKing80	자동 인형 (IOI18_doll)	C++17	100 / 100	214 ms	175448 KiB

doll

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

using namespace std;

vector<int> ansX, ansY, ansLegit;
int maxx = 1;

void build(int loc, vector<int> a, int elSt) {
	vector<int> l, r;
	if ((int)a.size() <= elSt)
		r = a;
	else {
		vector<bool> ocup(a.size(), false);
		int cnt = a.size() - elSt;
		for (int i = a.size() - 2; cnt; i -= 2, cnt --) {
			l.push_back(a[i]);
			ocup[i] = 1;
		}
		reverse(l.begin(), l.end());
		for (int i = 0; i < (int)a.size(); i ++)
			if (!ocup[i])
				r.push_back(a[i]);
	}
	if (elSt == 1) {
		if (!l.empty())
			ansX[-loc - 1] = l[0];
		else
			ansX[-loc - 1] = -1;

		if (!r.empty())
			ansY[-loc - 1] = r[0];
		else
			ansY[-loc - 1] = -1;
			
		return;
	}
	if (!l.empty()) {
		ansX[-loc - 1] = -(++ maxx);
		build(-maxx, l, elSt / 2);
	}
	else
		ansX[-loc - 1] = -1;
	if (!r.empty()) {
		ansY[-loc - 1] = -(++ maxx);
		build(-maxx, r, elSt / 2);
	}
	else
		ansY[-loc - 1] = -1;
}

vector<int> Ah;
vector<bool> state;
int loc = -1;
void parc(int nod) {
	if (loc >= (int)Ah.size() - 1)
		return;
	if (state[-nod - 1] == false) {
		state[-nod - 1] = true;
		if (ansX[-nod - 1] >= 0)
			ansX[-nod - 1] = Ah[++ loc], parc(-1);
		else
			parc(ansX[-nod - 1]);
	}
	if (state[-nod - 1] == true) {
		state[-nod - 1] = false;
		if (ansY[-nod - 1] >= 0)
			ansY[-nod - 1] = Ah[++ loc], parc(-1);
		else
			parc(ansY[-nod - 1]);
	}
}

void create_circuit(int m, vector<int> a) {
	a.push_back(0);
	int n = a.size();
	ansLegit.resize(m + 1);
	ansX.resize(10 * n + 100);
	ansY.resize(10 * n + 100);
	for (int i = 0; i <= m; i ++)
		ansLegit[i] = -1;
	int x = 1;
	while (2 * x < n)
		x *= 2;
	build(-1, a, x);
	Ah = a;
	ansX.resize(maxx);
	ansY.resize(maxx);
	state.resize(maxx, 0);
	parc(-1);
	answer(ansLegit, ansX, ansY);
}

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