Submission #832515

#	Time	Username	Problem	Language	Result	Execution time	Memory
832515		Antekb	Fun Tour (APIO20_fun)	C++17	21 / 100	449 ms	15596 KiB

fun

#include<bits/stdc++.h>
#include "fun.h"
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=2e5+5;
bool czy[N];
int gleb[N];
int find_dist(int v){
	//deb("a");
	if(v==1)return 0;
	return max(find_dist(v/2)+1, gleb[v^1]+2);
}
void upd(int v){
	//deb("b");
	if(!czy[v]){
		gleb[v]=-1e9;
	}
	else{
		gleb[v]=0;
		if(czy[v+v])gleb[v]=max(gleb[v], gleb[v+v]+1);
		if(czy[v+v+1])gleb[v]=max(gleb[v], gleb[v+v+1]+1);
	}
}
int find(int v, int dist, int t){
	//deb("c");deb(v, dist, t);
	if(v){
		//deb(v, dist, t)
	}
		if(dist==0)return v;
	if(t){
		if(gleb[v+v]==dist-1)return find(v+v, dist-1, 1);
		else return find(v+v+1, dist-1, 1);
	}
	if(dist==gleb[v^1]+2)return find(v^1, dist-2, 1);
	return find(v/2, dist-1, 0);
}

std::vector<int> createFunTour(int n, int Q) {
	//int H = hoursRequired(0, N - 1);
	//int A = attractionsBehind(0, N - 1);
	for(int i=n; i>0; i--){
		czy[i]=1;
		upd(i);
	}
	vi ans;
	ans.pb(n);
	while(ans.size()<n-1){
		czy[ans.back()]=0;
		int v=ans.back();
		//deb(v);
		while(v){
			upd(v);
			v/=2;
		}
		int d=find_dist(ans.back());
		//deb(d);
		v=find(ans.back(), d, 0);
		ans.pb(v);
	}
	czy[ans.back()]=0;
	for(int i=1; i<=n; i++){
		if(czy[i])ans.pb(i);
	}
	for(int &i:ans){
		deb(i);
		i--;
	}
	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:70:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |  while(ans.size()<n-1){
      |        ~~~~~~~~~~^~~~

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