Submission #442598

#	Time	Username	Problem	Language	Result	Execution time	Memory
442598		vanic	Mechanical Doll (IOI18_doll)	C++14	11 / 100	85 ms	12776 KiB

doll

#include "doll.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=1e5+5, Log=17, pot=(1<<Log);

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;*/
}

void rijesi(){
	int br;
	int pos=-1;
	int bit;
	int raz, ind;
	for(int i=1; i<=m; i++){
//		cout << "usao" << endl;
		if(sus[i].empty()){
			vez.push_back(0);
		}
		else if(sus[i].size()==1){
			vez.push_back(sus[i][0]);
		}
		else{
			vez.push_back(pos);
			br=1;
			bit=0;
			while((int)sus[i].size()>br){
				br*=2;
				bit++;
			}
			red.clear();
			napravi(bit);
			for(int j=1; j<br/2; j++){
				x.push_back(pos-j*2+1);
				y.push_back(pos-j*2);
			}
			raz=br-sus[i].size();
			ind=0;
			for(int j=br/2; j<br; j++){
				x.push_back(pos);
				y.push_back(pos);
			}
//			cout << "raz " << raz << endl;
			for(int j=raz; j<br; j++){
				if(red[j]&1){
//					cout << "y " << pos+br/2+red[j]/2 << endl;
					y[pos+br/2+red[j]/2]=sus[i][ind];
					ind++;
				}
				else{
//					cout << "x " << pos+br/2+red[j]/2 << endl;
					x[pos+br/2+red[j]/2]=sus[i][ind];
					ind++;
				}
			}
			pos-=br-1;
		}
	}
}

void create_circuit(int M, vector <int> a){
	m=M;
	n=a.size();
	vez.push_back(a[0]);
	for(int i=0; i<n-1; i++){
		sus[a[i]].push_back(a[i+1]);
	}
	sus[a[n-1]].push_back(0);
	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: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 0 / 56