Submission #500012

#	Time	Username	Problem	Language	Result	Execution time	Memory
500012		sidon	Mechanical Doll (IOI18_doll)	C++17	0 / 100	3 ms	4556 KiB

doll

#include <bits/stdc++.h>
using namespace std;
#include "doll.h"

vector<int> s, x(1<<18), y(1<<18), a;
int cnt, v, b, ind, rt;

int next() {
	int j = 0;
	for(int k = 0; k < b; k++)
		if(v & (1<<k)) j |= 1<<(b-k-1);
	s[j+=ind] = -rt-1, ++v;
	return j;
}

int dfs(int l, int r, int u) {
	if(r - l  > 2) {
		int m = (l + r) / 2;
		x[u] = -1-dfs(l, m, cnt++);
		y[u] = -1-dfs(m, r, cnt++);
	} else {
		x[u] = a[next()];
		y[u] = a[next()];
	}
	return u;
}

void create_circuit(int M, vector<int> A) {
	int N = A.size();
	s.resize(M+1), a = A;

	for(b = 0; b < 20; b++){
		if(N & (1<<b)){
			s[rt] = -cnt++-1;
			rt = cnt-1, v = 0;

			dfs(0, 1<<b, rt);
			rt = a[(ind+=1<<b)-1];
		}
	}
	s[rt] = 0;
	x.resize(cnt);
	y.resize(cnt);

	answer(s, x, y);
}

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