제출 #407118

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

doll

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

using namespace std;

vector<int> C, X, Y, v;
vector<vector<int>> vecs;

void make_batch(int k, vector<int> d) { // Makes a batch of 2^n thingies
	for(int i = 0; i < k; i++) {
		int x = (1 << i);
		if(i < k-1) {
			int z = X.size() + x;
			for(int j = 0; j < (int)x; j++) {
				X.push_back(-(z+2*j+1));
				Y.push_back(-(z+2*j+2));
			}
		}
		else {
			int m = X.size();
			for(int j = 0; j < (int)x; j++) {
				X.push_back(0);
				Y.push_back(0);
			}
			for(int j = 0; j < (int)d.size(); j++) {
				int pl = 0;
				for(int l = 0; l < k; l++) {
					if(j & (1 << l)) pl += (1 << (k-l-1));
				}
				pl = d.size() - pl - 1;
				if(pl%2) Y[m + pl/2] = d[j];
				else X[m + pl/2] = d[j];
			}
		}
	}
	return;
}

void print() {
	for(int i = 0; i < (int)C.size(); i++) cout << C[i] << ' ';
	cout << '\n';
	for(int i = 0; i < (int)X.size(); i++) cout << X[i] << ' ';
	cout << '\n';
	for(int i = 0; i < (int)Y.size(); i++) cout << Y[i] << ' ';
	cout << '\n';
	for(int i = 0; i < (int)v.size(); i++) cout << v[i] << ' ';
	cout << '\n';
	for(int i = 0; i < (int)v.size(); i++) {
		for(int j = 0; j < (int)vecs[i].size(); j++) {
			cout << vecs[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}

void create_circuit(int m, vector<int> a) {
	vector<int>().swap(C);
	vector<int>().swap(X);
	vector<int>().swap(Y);
	vector<int>().swap(v);
	vector<vector<int>>().swap(vecs);
	int k = 69;
	int n = a.size();
	for(int i = 0; i < 20; i++) {
		if(n & (1 << i)) {
			k = i;
		}
	}
	int p = 1;
	v.resize(k+1);
	vecs.resize(k+1);
	Y.resize(k+1);
	for(int i = 0; i <= k; i++) {
		if(i == k) X.push_back(0);
		else X.push_back(-i-2);
		if(n & (1 << (k-i))) {
			p++;
			v[i] = 1;
		}
		else v[i] = 0;
	}
	p = 0;
	for(int i = 1; i < (1 << (k+1)); i++) {
		for(int j = 0; j <= k; j++) {
			if(i & (1 << j)) {
				if(v[j]) {
					vecs[j].push_back(a[p]);
					p++;
				}
				break;
			}
		}
	}
	p = k;
	for(int i = 0; i <= k; i++) {
		if(i == k) {
			if(v[i]) Y[i] = vecs[i][0];
			else Y[i] = -1;
		}
		else if(v[i]) {
			Y[i] = (int)Y.size() * -1 - 1;
			make_batch(k-i, vecs[i]);
		}
		else Y[i] = -1;
	}
	for(int i = 0; i <= m; i++) C.push_back(-1);
	// print();
	answer(C, Y, X);
}

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