제출 #996450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996450		Dan4Life	즐거운 행로 (APIO20_fun)	C++17	0 / 100	4 ms	10076 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) {
	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