Submission #1026101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026101		Lalic	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	73 ms	11156 KiB

doll

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

int cnt, m;

void add(int ver, int root, int depth, int& tot, vector<int>& X, vector<int>& Y, vector<int>& state){
	if(!tot){
		if(Y[ver-m-1]==-1) Y[ver-m-1]=root;
		if(X[ver-m-1]==-1) X[ver-m-1]=root;
		return;
	}
	
	if(!depth){
		tot--;
		if(!tot) X[ver-m-1]=root;
		else tot--;
		return;
	}
	
	Y[ver-m-1]=++cnt;
	X.pb(-1); Y.pb(-1);
	state.pb(0);
	add(cnt, root, depth-1, tot, X, Y, state);
	
	if(!tot) X[ver-m-1]=root;
	else{
		X[ver-m-1]=++cnt;
		X.pb(-1); Y.pb(-1);
		state.pb(0);
		add(cnt, root, depth-1, tot, X, Y, state);
	}
}

void calc(int p, int qnt, vector<int>& C, vector<int>& X, vector<int>& Y, vector<int>& state){
	if(qnt==1) return;
	
	int cam=0;
	
	while((1<<cam)<qnt) cam++;
	
	C[p]=++cnt;
	X.pb(-1); Y.pb(-1);
	state.pb(0);
	
	add(cnt, cnt, cam-1, qnt, X, Y, state);
}

void create_circuit(int M, vector<int> A) {
	cnt=M;
	m=M;
	
	A.pb(0);
	vector<int> C(M+1, -1), X, Y, freq(M+1, 0), state;
	for(auto u : A) freq[u]++;
	
	int curr=0;
	for(auto u : A){
		if(C[curr]==-1) calc(curr, freq[curr], C, X, Y, state);
		
		if(C[curr]==-1){
			C[curr]=u;
			curr=u;
			continue;
		}
		
		curr=C[curr];
		
		while(1){
			if(!state[curr-m-1]){
				state[curr-m-1]=1-state[curr-m-1];
				
				if(X[curr-m-1]==-1){
					X[curr-m-1]=u;
					break;
				}
				else curr=X[curr-m-1];
			}
			else{
				state[curr-m-1]=1-state[curr-m-1];
				
				if(Y[curr-m-1]==-1){
					Y[curr-m-1]=u;
					break;
				}
				else curr=Y[curr-m-1];
			}
		}
		
		curr=u;
	}
	
	for(auto& u : C){
		if(u>m) u=m-u;
		else if(u==-1) u=0;
	}
	for(auto& u : X)
		if(u>m) u=m-u;
	for(auto& u : Y)
		if(u>m) u=m-u;
	
	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: 41.5530038336 / 56