Submission #139883

#	Time	Username	Problem	Language	Result	Execution time	Memory
139883		almogwald	Mechanical Doll (IOI18_doll)	C++14	84 / 100	142 ms	8868 KiB

doll

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
//#include "job.h"
#include "doll.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;

void create_circuit(int M, std::vector<int> A) {
	int N = A.size();
	std::vector<int> C(M + 1);
	C[0] = A[0];
	for (int i = 1; i <= M; ++i) {
		C[i] = -1;
	}

	vector<int> x, y;
	if(N==1){
		x.push_back(-1);
		y.push_back(0);
		answer(C, x, y);
	}
	A.push_back(0);
	int num=0;
	while(1<<num < N){
		num++;
	}
	veci depth,state;
	depth.push_back(num);
	x.push_back(0);
	state.push_back(0);
	y.push_back(0);
	int cur=0;
	int n=N;
	while(depth[cur]>1){
		if(n+(1<<(depth[cur]-1))<=(1<<num)){
			x[cur]=-1;
			n+=1<<(depth[cur]-1);
		}else{
			x[cur]=-(1+x.size());
			depth.push_back(depth[cur]-1);
				x.push_back(0);
				state.push_back(0);
				y.push_back(0);
		}
		y[cur]=-(1+x.size());
					depth.push_back(depth[cur]-1);
						x.push_back(0);
						state.push_back(0);
						y.push_back(0);
						cur++;
	}
	if(n<(1<<num)){
		x[cur]=-1;
	}
	int p=1;
	cur=-1;
	while(p<=N){
		int lcur=-cur-1;
		state[lcur]=1-state[lcur];
		if(state[lcur]){
			lcur=x[lcur];
		}else{
			lcur=y[lcur];
		}
		if(lcur==0){
			lcur=-cur-1;
			if(state[lcur]){
				x[lcur]=A[p++];
			}else{
				y[lcur]=A[p++];
			}
			lcur=-1;
		}
		cur =lcur;
	}
	answer(C, x, y);
}

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