Submission #442561

#	Time	Username	Problem	Language	Result	Execution time	Memory
442561		vanic	Mechanical Doll (IOI18_doll)	C++14	6 / 100	105 ms	14272 KiB

doll

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

using namespace std;

const int maxn=1e5+5;

vector < int > sus[maxn];
vector < int > vez;
vector < int > x, y;
int m, n;

void rijesi(){
	int br;
	int pos=-1;
//	int raz;
	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;
			while((int)sus[i].size()>br){
				br*=2;
			}
			for(int j=1; j<br/2; j++){
				x.push_back(pos-j*2);
				y.push_back(pos-j*2-1);
			}
//			raz=br-sus[i].size();
			for(int j=br/2; j<br; j++){
				if((j-br/2)*2<(int)sus[i].size()){
					x.push_back(sus[i][(j-br/2)*2]);
				}
				else{
					x.push_back(pos);
				}
				if((j-br/2)*2+1<(int)sus[i].size()){
					y.push_back(sus[i][(j-br/2)*2+1]);
				}
				else{
					y.push_back(pos);
				}
			}
			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] << ' ';
	}*/
	
	answer(vez, x, y);
}

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