Submission #1042234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042234		amunduzbaev	Mechanical Doll (IOI18_doll)	C++17	10 / 100	106 ms	13008 KiB

doll

#include "doll.h"

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

void create_circuit(int m, vector<int> a) {
	vector<int> c(m + 1, -1);
	//~ for(auto x : a){
		//~ cout<<x<<" ";
	//~ } cout<<endl;
	
	c[0] = a[0];
	a.erase(a.begin());
	//~ a.push_back(0);
	
	//~ for(auto x : a){
		//~ cout<<x<<" ";
	//~ } cout<<endl;
	
	//~ cout<<"Been here: 1"<<endl;
	
	int n = a.size() + 1;
	int x_ = __lg(n);
	
	if((1 << x_) < n) x_++;
	
	vector<int> x, y;
	int last = 0;
	
	auto get = [&](){
		x.push_back(0);
		y.push_back(0);
		last++;
		
		return last;
	};
	
	//~ cout<<"Been here: 2"<<endl;
	
	function<int(int, int, vector<int>)> buildTree = [&](int l, int r, vector<int> a){
		//~ cout<<l<<" "<<r<<" : ";
		//~ for(auto x : a) cout<<x<<" ";
		//~ cout<<endl;
		
		if((int)a.size() == 0){
			if(r == (1 << x_) - 1){
				if(l == r) return 0;
				
				int m = (l + r) >> 1;
				int root = get();
				
				x[root - 1] = -1;
				y[root - 1] = buildTree(m + 1, r, a);
				
				//~ cout<<"vertex: "<<-root<<" "<<x[root - 1]<<" "<<y[root - 1]<<endl;
				
				return -root;
			}
			
			return -1;
		}
		if(l == r){
			assert((int)a.size() == 1);
			return a[0];
		}
		
		int m = (l + r) >> 1;
		int l_sz = m - l + 1;
		// [l, m], [m + 1, r]
		
		int goRight = (int)a.size() - l_sz;
		vector<int> goL, goR;
		
		for(int i=0;i<(int)a.size();i++){
			if(i % 2 == 0 || (int)goR.size() == goRight){
				goL.push_back(a[i]);
			} else {
				goR.push_back(a[i]);
			}
		}
		
		int root = get();
		
		//~ int LeftRoot = buildTree(l, m, goL);
		//~ int RightRoot = buildTree(m + 1, r, goR);
		
		//~ cout<<"before: " <<LeftRoot<<" "<<RightRoot<<endl;
		
		x[root - 1] = buildTree(l, m, goL);
		y[root - 1] = buildTree(m + 1, r, goR);
		
		//~ x[root - 1] = LeftRoot;
		//~ y[root - 1] = RightRoot;
		
		//~ cout<<"vertex: "<<-root<<" "<<x[root - 1]<<" "<<y[root - 1]<<endl;
		
		return -root;
		//~ buildTree(l, m, goL);
		//~ buildTree(m + 1, r, goR);
	};
	
	buildTree(0, (1 << x_) - 1, a);
	
	vector<int> dir(last, 0);
	
	function<int(int, int)> simulate = [&](int root, int value){
		//~ cout<<root<<" "<<value<<endl;
		if(root >= 0){
			return value;
		}
		
		root = -root;
		
		dir[root - 1] ^= 1;
		if(dir[root - 1] != 0){
			x[root - 1] = simulate(x[root - 1], value);
		} else {
			y[root - 1] = simulate(y[root - 1], value);
		}
		
		return -root;
	};
	
	for(int i=0;i<(int)a.size();i++){
		simulate(-1, a[i]);
	}
	
	//~ for(int i=0;i<(int)a.size();i++){
		//~ cout<<a[i]<<" ";
	//~ } cout<<"\n";
	
	//~ for(int i=0;i<=m;i++){
		//~ cout<<c[i]<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=0;i<last;i++){
		//~ cout<<x[i]<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=0;i<last;i++){
		//~ cout<<y[i]<<" ";
	//~ } cout<<endl;
	
	assert(last <= n + x_ * 2);
	
	answer(c, x, y);
	
	return;
}

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