Submission #442856

#	Time	Username	Problem	Language	Result	Execution time	Memory
442856		vanic	Mechanical Doll (IOI18_doll)	C++14	100 / 100	108 ms	13104 KiB

doll

#include "doll.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
 
using namespace std;
 
const int maxn=1e5+5, Log=17, pot=(1<<Log), inf=1e9;
 
vector < int > vez;
vector < int > x, y;
int m, n;
vector < int > red;
 
void napravi(int bit){
	int br=0;
	for(int i=0; i<(1<<bit); i++){
		red.push_back(br);
		for(int j=bit-1; j>-1; j--){
			if((1<<j)&br){
				br-=(1<<j);
			}
			else{
				br+=(1<<j);
				break;
			}
		}
	}
/*	for(int i=0; i<red.size(); i++){
		cout << red[i] << ' ';
	}
	cout << endl;*/
}
 
int bit;
int poz;
int mini;
int tren;
 
struct Logaritamska{
	vector < int > l;
	int siz;
	void precompute(int sz){
		siz=sz;
		l.clear();
		while(sz--){
			l.push_back(0);
		}
	}
	void update(int x, int val){
		for(; x<siz; x+=(x & -x)){
			l[x]+=val;
		}
	}
	int query(int x){
		int sol=0;
		for(; x>0; x-=(x & -x)){
			sol+=l[x];
		}
		return sol;
	}
};
 
 
Logaritamska L;
 
 
vector < int > A;
 
int siri(int cor, int val, int dep, int pos){
	if(bit==dep){
//		cout << red[cor] << endl;
		if(L.query(red[cor]+1)==L.query(red[cor])){
			int ind=red[cor]-L.query(red[cor]);
			return A[ind];
		}
		else{
			return inf;
		}
	}
	int a, b;
	x.push_back(0);
	y.push_back(0);
	mini=min(mini, val);
	a=siri(cor, val-1, dep+1, pos);
	b=siri(cor+(1<<(bit-dep-1)), mini-1, dep+1, pos);
	if(a==inf && b==inf){
		x.pop_back();
		y.pop_back();
		if(mini==val){
			mini++;
		}
		return inf;
	}
	if(b==inf){
		b=pos;
	}
	else if(a==inf){
		a=pos;
	}
	x[-1-val]=a;
	y[-1-val]=b;
	return val;
}
 

void rijesi(){
	int br;
	int raz;
	br=1;
	bit=0;
	for(int i=0; i<m+1; i++){
		vez.push_back(-1);
	}
	while((int)A.size()>br){
		br*=2;
		bit++;
	}
	red.clear();
	napravi(bit);
	L.precompute(br+5);
	raz=br-A.size();
	for(int j=0; j<raz; j++){
		L.update(red[j]+1, 1);
	}
	siri(0, -1, 0, -1);
}
 
void create_circuit(int M, vector <int> a){
	m=M;
	n=a.size();
	a.push_back(0);
	A=a;
	rijesi();
/*	for(int i=0; i<(int)vez.size(); i++){
		cout << vez[i] << ' ';
	}
	cout << endl;
	for(int i=0; i<(int)x.size(); i++){
		cout << x[i] << ' ' << y[i] << endl;
	}*/
	answer(vez, 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