Submission #788952

#	Time	Username	Problem	Language	Result	Execution time	Memory
788952		ToniB	자동 인형 (IOI18_doll)	C++17	46 / 100	101 ms	16360 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
const int MAXN = 400000;

int n, m, cur = 1, s, x[MAXN], y[MAXN];
vector<int> a;
vector<int> c, x_ans, y_ans;

void dfs(int node, vector<int> v){
	cur = max(cur, node);
	if(v.size() == 2){
		x[node - 1] = v[0];
		y[node - 1] = v[1];
		return ;
	}
	x[node - 1] = -node * 2;
	y[node - 1] = -(node * 2 + 1);

	vector<int> L, R;
	for(int i = 0; i < (int)v.size(); ++i){
		if(i & 1) R.push_back(v[i]);
		else L.push_back(v[i]);
	}
	dfs(node * 2, L);
	dfs(node * 2 + 1, R);
}

void create_circuit(int _m, vector<int> _a){
	m = _m; a = _a; n = a.size();
	if(m == 1){
		int p = 0;
		while((1 << p) <= n) ++p;
		c = {-p, -p};
		x_ans.resize(p); y_ans.resize(p);
		int sum = 0;
		for(int i = p - 1; i >= 0; --i){
			if(n & 1 << i){
				x_ans[i] = 1;
				sum += 1 << i;
			}
			else x_ans[i] = -p;
			y_ans[i] = -i;
		}
		answer(c, x_ans, y_ans);
		return ;
	}
	for(int i = 0; i <= m; ++i) c.push_back(-1);
	int p = 1;
	while(p < n + 1){
		p *= 2;
	}
	for(int i = n + 1; i < p; ++i) a.push_back(-1);
	a.push_back(0);
	dfs(1, a);
	x_ans.resize(cur); y_ans.resize(cur);
	for(int i = 0; i < cur; ++i){
		x_ans[i] = x[i];
		y_ans[i] = y[i];
	}
	answer(c, x_ans, y_ans);
}

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