Submission #442842

#	Time	Username	Problem	Language	Result	Execution time	Memory
442842		vanic	Mechanical Doll (IOI18_doll)	C++14	85.55 / 100	137 ms	15544 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 > sus[maxn];
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;
 
 
 
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 sus[tren][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 pos=-1;
	int raz;
	for(int i=1; i<=m; i++){
//		cout << "usao" << endl;
		tren=i;
		if(sus[i].empty()){
			vez.push_back(0);
		}
		else if(sus[i].size()==1){
			vez.push_back(sus[i][0]);
		}
		else{
			br=1;
			bit=0;
			while((int)sus[i].size()>br){
				br*=2;
				bit++;
			}
			red.clear();
			napravi(bit);
			L.precompute(br+5);
			raz=br-sus[i].size();
//			cout << "raz " << raz << endl;
			for(int j=0; j<raz; j++){
//				cout << "ne " << red[j] << endl;
				L.update(red[j]+1, 1);
			}
//			cout << "proso" << endl;
			vez.push_back(siri(0, pos, 0, pos));
			pos=mini-1;
		}
	}
}
 
void create_circuit(int M, vector <int> a){
	m=M;
	n=a.size();
	a.push_back(0);
	vez.push_back(a[0]);
	for(int i=0; i<n; i++){
		sus[a[i]].push_back(a[i+1]);
	}
	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: 41.5530038336 / 56