Submission #996452

#	Time	Username	Problem	Language	Result	Execution time	Memory
996452		Dan4Life	Fun Tour (APIO20_fun)	C++17	0 / 100	2 ms	5212 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) begin(a),end(a)
#define sz(a) (int)a.size()
#define pb push_back

const int mxN = (int)1e5+10;
vector<int> ans; 
bool vis[mxN];

set<pair<int,int>> S[mxN];

void add(int x){
	ans.pb(x-1); vis[x]=true;
	//cout << x << " ";
	// remove x from the tree
	int par = x, dis = 0;
	while(par){
		S[par].erase({dis,x});
		if(par==1) break;
		par/=2, dis++;
	}
}

int find_farthest(int x){
	int par = x/2, pre=x, pre2=-1;
	while(par){
		if(vis[par]) break; 
		if(par==1) break;
		pre2 = pre; pre=par; par/=2;
	}
	int other_subtree;
	if(vis[par]){
		par = pre;
		other_subtree = par*2;
		if(pre2==other_subtree) other_subtree++;
	}
	else{
		other_subtree = par*2;
		if(pre==other_subtree) other_subtree++;
	}
	
	if(vis[other_subtree]) return par;
	
	return prev(end(S[other_subtree]))->second;
}

vector<int> createFunTour(int N, int Q) {
	if(N==2) return {1,0};
	ans.clear(); vis[0]=1;
	for(int i = 1; i <= N; i++){
		int par = i, dis = 0;
		while(par){
			S[par].insert({dis,i});
			if(par==1) break;
			par/=2, dis++;
		}
	}
	int x = N; add(x);
	while(sz(ans)!=N) x = find_farthest(x), add(x);
	return ans;
}

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