Submission #402579

#	Time	Username	Problem	Language	Result	Execution time	Memory
402579		faresbasbs	Fun Tour (APIO20_fun)	C++14	0 / 100	6 ms	6348 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
using namespace std;
int n,bad[300001],h[100001];
multiset<int> ms[100001];

void dfs(int curr , int hi){
	h[curr] = hi;
	ms[curr].insert(hi);
	for(int i = 2*curr+1 ; i <= 2*curr+2 ; i += 1){
		if(i >= n){
			continue;
		}
		dfs(i,hi+1);
		for(auto j : ms[i]){
			ms[curr].insert(j);
		}
	}
}

int solve(int curr){
	bad[curr] = 1;
	int from = -1 , root = curr;
	while(curr && !bad[(curr-1)/2]){
		from = curr;
		ms[curr].erase(ms[curr].find(h[root]));
		curr = (curr-1)/2;
	}
	ms[curr].erase(ms[curr].find(h[root]));
	// cout << curr << endl;
	if(from == -1){
		for(int i = 2*curr+1 ; i <= 2*curr+2 ; i += 1){
			if(!bad[i]){
				from = i;
			}
		}
	}else{
		if(from == 2*curr+1){
			from += 1;
		}else{
			from -= 1;
		}
	}
	if(bad[from]){
		return curr;
	}
	curr = from;
	while(true){
		bool g = 0;
		for(int i = 2*curr+1 ; i <= 2*curr+2 ; i += 1){
			if(bad[i]){
				continue;
			}
			if(*(--ms[i].end()) == *(--ms[curr].end())){
				g = 1;
				curr = i;
				break;
			}
		}
		if(!g){
			break;
		}
	}
	return curr;
}

vector<int> createFunTour(int N , int Q){
	n = N;
	for(int i = n ; i <= 300000 ; i += 1){
		bad[i] = 1;
	}
	dfs(0,0);
	vector<int> ret = {n-1};
	for(int i = 0 ; i < n-1 ; i += 1){
		ret.push_back(solve(ret.back()));
	}
	return ret;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34