Submission #596127

#	Time	Username	Problem	Language	Result	Execution time	Memory
596127		FatihSolak	Mechanical Doll (IOI18_doll)	C++17	100 / 100	147 ms	11100 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#define N 300005
using namespace std;
int x[N],y[N];
bool last[N];
int add;
void solve(int now,int needed,int num){
	//cout << now << " " << needed << " " << num << endl;
	assert(needed);
	if(num == 2){
		if(needed == 1){
			y[now] = -2;
			x[now] = 1e9;
		}
		if(needed == 2){
			x[now] = 1e9;
			y[now] = 1e9;
		}
		return;
	}
	int nwlen = num/2;
	add++;
	y[now] = -add;
	solve(add,min(needed,nwlen),nwlen);
	needed -= min(needed,nwlen);
	if(needed == 0){
		x[now] = -2;
	}
	else{
		add++;
		x[now] = -add;
		solve(add,min(needed,nwlen),nwlen);
	}
}
void create_circuit(int M, vector<int> A) {
	int n = A.size();
	vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}
	if(n == 1){
		C[A[0]] = 0;
		answer(C, {0}, {0});
		return;
	}
	A.push_back(0);
	x[2] = -2;
	y[2] = -1;
	int num = 1;
	while(num < n)
		num *= 2;
	add = 2;
	solve(1,n,num);
	int cnt = 0;
	int pos = 0;
	while(cnt < n){
		//cout << pos << endl;
		if(pos >= 0){
			pos = C[pos];
		}
		else{
			pos *= -1;
			if(last[pos] == 0){
				last[pos] = 1;
				if(x[pos] == 1e9){
					cnt++;
					x[pos] = A[cnt];
				}
				pos = x[pos];
			}
			else{
				last[pos] = 0;
				if(y[pos] == 1e9){
					cnt++;
					y[pos] = A[cnt];
				}
				pos = y[pos];
			}
		}
	}
	vector<int> X,Y;
	for(int i = 1;i<=add;i++){
		X.push_back(x[i]);
		Y.push_back(y[i]);
	}
	// for(auto u:C){
	// 	cout << u << " ";
	// }
	// cout << endl;
	// for(auto u:X){
	// 	cout << u << " ";
	// }
	// cout << endl;
	// for(auto u:Y){
	// 	cout << u << " ";
	// }
	// cout << endl;
	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: 56 / 56