Submission #433905

#	Time	Username	Problem	Language	Result	Execution time	Memory
433905		AugustinasJucas	Mechanical Doll (IOI18_doll)	C++14	37 / 100	188 ms	12336 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
int m;
vector<int> eil;
const int dydis = 800000 + 1100;
int state[dydis] = {};
int X[dydis];
int Y[dydis];
int n;
int dbInd = 0;

int closestPower(int a){
	for(int i = a+1; i <= a * 3 + 2; i++){
		if(__builtin_popcount(i) == 1) return i;
	}
	return -1;
}
int dfs(int v){
	if(v >= n){
		int ret = 0;
		if(dbInd == (int)eil.size()) {
			ret = -1;
		}else{
			ret = eil[dbInd++];
		}
		//cout << "dabar " << ret << "\n";
		return ret;
	}else{
		int sk = dfs(v*2 + state[v]);
		if(state[v] == 0) X[v-1] = sk;
		else Y[v-1] = sk;
		state[v] = !state[v];
		return -v;
	}
}
void create_circuit(int M, vector<int> A) {
	eil = A;
	vector<int> C(M+1, -1); C[0] = -1;
	n = closestPower(A.size());
	//cout << "n = " << n << endl;
	for(int i = 0; i < n; i++) dfs(1);
	vector<int> XX; 
	for(int i = 0; i < n-1; i++){
		XX.push_back(X[i]);
		//cout << -(i+1) << " x-as yra " << X[i] << endl;
	}
	vector<int> YY; 
	for(int i = 0; i < n-1; i++) {
		YY.push_back(Y[i]);
		//cout << -i - 1 << " y-as yra " << Y[i] << endl;
	}
	
	YY[YY.size()-1] = 0;
	
//	cout << "arciausias " << A.size() << " laipsnis yra " << n << endl;
	answer(C, XX, YY);
	return ;
}

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