Submission #996461

#	Time	Username	Problem	Language	Result	Execution time	Memory
996461		Dan4Life	Fun Tour (APIO20_fun)	C++17	0 / 100	1 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];
int n;
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, pre=x;
	while(par){
		if(vis[par/2]) break;
		pre=par; par/=2;
	}
	int other_subtree;
	if(vis[par]){
		other_subtree = x;
		return prev(end(S[other_subtree]))->second;
	}
	else{
		other_subtree = par*2;
		if(pre==other_subtree) other_subtree++;
		if(other_subtree>n) return par;
		if(vis[other_subtree]) return par;
		return prev(end(S[other_subtree]))->second;
	}
}

vector<int> createFunTour(int N, int Q) {
	ans.clear(); vis[0]=1; n = N;
	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