Submission #260024

#	Time	Username	Problem	Language	Result	Execution time	Memory
260024		ChrisT	Mechanical Doll (IOI18_doll)	C++17	53 / 100	166 ms	13112 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
void create_circuit (int m, vector<int> a) {
	int n = a.size();
	vector<vector<int>> togo(m+1); vector<int> exit(m+1),x,y;
	int lst = 0;
	for (int i = 0; i < n; i++) {
		togo[lst].push_back(a[i]);
		lst = a[i];
	}
	togo[lst].push_back(0);
	for (int j = 0; j <= m; j++) {
		if (togo[j].empty()) exit[j] = j;
		else if (togo[j].size() == 1) exit[j] = togo[j][0];
		else {
			int levels = __lg((int)togo[j].size() - 1) + 1, base = (int)x.size();
			x.resize(base + (1 << levels) - 1);
			y.resize(base + (1 << levels) - 1); vector<int> val(1 << levels); val[1] = 0;
			exit[j] = -(base + 1);
			for (int i = 1; i < (1 << (levels - 1)); i++) {
				x[base + i - 1] = -(base + i * 2);
				val[i*2] = val[i];
				y[base + i - 1] = -(base + i * 2 + 1);
				val[i*2+1] = val[i] | (1 << __lg(i));
			}
			int lower = (1 << levels) - (int)togo[j].size();
			for (int i = (1 << (levels-1)); i < (1 << levels); i++) {
				int lVal = val[i], rVal = val[i] | (1 << __lg(i));
				if (lVal >= lower) x[base + i - 1] = togo[j][lVal - lower];
				else x[base + i - 1] = -(base + 1);
				if (rVal >= lower) y[base + i - 1] = togo[j][rVal - lower];
				else y[base + i - 1] = -(base + 1); 
			}
		}
	}
	answer(exit,x,y);
}

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