Submission #858903

#	Time	Username	Problem	Language	Result	Execution time	Memory
858903		waldi	Mechanical Doll (IOI18_doll)	C++17	100 / 100	65 ms	10956 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int(x.size()))
using namespace std;

void create_circuit(int m, vector<int> a){
	int n = a.size();
	int N = 1;
	while(N <= n) N <<= 1;
	int pierwszy = N-n-1;
	
	vector<int> perm(N, 0);
	FOR(i, 1, N-1) perm[i] = (perm[i>>1]>>1) + (i&1 ? (N>>1) : 0);
	
	int iter = 0;
	vector<int> tab(N);
	REP(i, N) if(pierwszy <= perm[i] && perm[i] < N-1) tab[perm[i]] = a[iter++];
	
	int it = 0;
	vector<int> x, y;
	auto nowy = [&](){
		x.emplace_back(0);
		y.emplace_back(0);
		++it;
	};
	function<void(int, int, int)> dfs = [&](int w, int lewo, int prawo){
		int sr = (lewo+prawo)>>1;
		
		//printf("w: %d\n", w);
		
		if(sr < pierwszy){
			x[-w-1] = -1;
		}
		else{
			if(lewo == sr){
				x[-w-1] = tab[lewo];
			}
			else{
				nowy();
				x[-w-1] = -it;
				dfs(-it, lewo, sr);
			}
		}
		
		if(sr+1 == prawo){
			if(prawo == N-1) y[-w-1] = 0;
			else y[-w-1] = tab[prawo];
		}
		else{
			nowy();
			y[-w-1] = -it;
			dfs(-it, sr+1, prawo);
		}
	};
	nowy();
	dfs(-1, 0, N-1);
	
	vector<int> c(m+1, -1);
	
	/*printf("c: ");
	for(int i : c) printf("%d ", i);
	printf("\n");
	
	printf("x: ");
	for(int i : x) printf("%d ", i);
	printf("\n");
	
	printf("y: ");
	for(int i : y) printf("%d ", i);
	printf("\n");*/
	
	answer(c, x, y);
}

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