Submission #828885

#	Time	Username	Problem	Language	Result	Execution time	Memory
828885		HamletPetrosyan	Mechanical Doll (IOI18_doll)	C++17	10 / 100	21 ms	19128 KiB

doll

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

#define len(a) ((int)(a).size())
#define pii pair<int, int>
#define fr first
#define sc second

int n, avl, logn;
vector<int> X, Y;
vector<pii> HRT;
int CNTR = -1, S = 0;

bool dfs(int v, int x, int y, int h){
	if(h >= logn - 1){
		HRT[y] = {v, x};
		HRT[y + (1 << (logn - 1))] = {v, x + 1};
		if(x + 1 < avl) return false;
		if(x < avl) X[-v - 1] = -1;
		S++;
		return true;
	}
	int rch = --CNTR;
	if(!dfs(rch, x + (1 << (logn - h - 1)), y + (1 << h), h + 1)) return false;
	Y[-v - 1] = rch;
	int lch = --CNTR;
	if(!dfs(lch, x, y, h + 1)){
		X[-v - 1] = -1;
		S++;
		return true;
	}
	X[-v - 1] = lch;
	S++;
	return true;
}

void create_circuit(int M, vector<int> A) {
	n = A.size();
	vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; ++i) C[i] = -1;
	logn = ceil(log2(n));
	avl = (1 << logn) - n;

	X.resize(4 * n);
	Y.resize(4 * n);
	HRT.resize(4 * n);
	dfs(-1, 0, 0, 0);

	X.resize(S);
	Y.resize(S);

	if(n == 1){
		C[A[0]] = 0;
		answer(C, X, Y);
		return;
	}

	// cout << avl << "\n";

	int avlcnt = 0;
	for(int i = 0, v, x, ind; i < len(HRT); i++){
		// cout << "(" << HRT[i].fr << ", " << HRT[i].sc << ") ";
		v = -HRT[i].fr - 1;
		x = HRT[i].sc;
		if(x < avl){
			avlcnt++;
			continue;
		}
		ind = i - avlcnt + 1;
		if(x % 2) Y[v] = (ind == n) ? 0 : A[ind];
		else X[v] = (ind == n) ? 0 : A[ind]; 
	}

	// cout << endl;
	// for(auto h : C) cout << h << " ";
	// cout << endl << endl;
	// for(auto h : X) cout << h << " ";
	// cout << endl;
	// for(auto h : Y) cout << h << " ";
	// cout << endl;

	answer(C, X, Y);
}

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