Submission #739812

#	Time	Username	Problem	Language	Result	Execution time	Memory
739812		sentheta	Mechanical Doll (IOI18_doll)	C++17	100 / 100	115 ms	14376 KiB

doll

#include "doll.h"
#include<vector>
#include<algorithm>
#include<utility>
#include<array>
#include<map>
#include<set>
#include<cassert>
#include<iostream>
using namespace std;
#define V vector
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define nl '\n'
#define _ << " " <<
#define dbg(x) cout << "?" << #x << " : " << x << endl;

const int N = 4e5+5;
const int B = 3;

int n, m;
V<int> a;
V<int> c, lc, rc;
int make(){
	lc.push_back(-1);
	rc.push_back(-1);
	return -(int)lc.size();
}
int f(int x){
	return -x-1;
}



V<int> leaves;
bool stat[N];

void create_circuit(int _m,V<int> _a){
	a.swap(_a); a.push_back(0);
	n = a.size(); m = _m;


	// build tree
	V<int> v(n,0);
	while(v.size() > 1){
		V<int> nxt;

		if(v.size()%2==1){
			int x=1, y=v[0];

			int z = make();
			lc[f(z)] = x; rc[f(z)] = y;
			nxt.push_back(z);
		}

		for(int i=v.size()%2; i<(int)v.size(); i+=2){
			int x=v[i], y=v[i+1];

			int z = make();
			lc[f(z)] = x; rc[f(z)] = y;
			nxt.push_back(z);
		}

		v.swap(nxt);
	}

	for(int x=-1; ; x--){
		int idx = -x-1;
		if(lc[idx]==1) lc[idx] = -lc.size();
		if(rc[idx]==1) rc[idx] = -rc.size();

		// cout << x _ lc[idx] _ rc[idx] << nl;
		if(x==-(int)lc.size()) break;
	}
	c = V<int>(m+1, -lc.size());

	// return;



	// simulate to find order of leaves
	// dbg("LEAVES");
	int x = -lc.size();
	while((int)leaves.size() < n){
		// dbg(x);
		int idx = -x-1, y;
		if(stat[idx]==0) y = lc[idx];
		else y = rc[idx];
		stat[idx] ^= 1;

		if(y==0){
			// cout << "LEAF" << nl;
			// dbg(x);
			leaves.push_back(x);
			x = -lc.size();
		}
		else{
			x = y;
		}
	}
	rep(i,0,N) stat[i] = 0;

	rep(i,0,n){
		x = leaves[i];
		int idx = -x-1;

		if(lc[idx]==0){
			lc[idx] = a[i];
		}
		else{
			rc[idx] = a[i];
		}
	}



	answer(c,lc,rc);
}

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