Submission #833036

#	Time	Username	Problem	Language	Result	Execution time	Memory
833036		Antekb	Fun Tour (APIO20_fun)	C++17	100 / 100	181 ms	27084 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());


std::vector<int> createFunTour(int n, int Q) {
	if(n==2)return {0, 1};
	//int H = hoursRequired(0, N - 1);
	//int A = attractionsBehind(0, N - 1);
	vi siz(n), dep(n), typ(n);
	siz[0]=n;
	int cent=0;
	for(int i=1; i<n; i++){
		siz[i]=attractionsBehind(0, i);
		if(2*siz[i]>=n && siz[i]<siz[cent])cent=i;
	}
	vi kto;
	for(int i=0; i<n; i++){
		if(i!=cent)dep[i]=hoursRequired(cent, i);
		if(dep[i]==1)kto.pb(i);
	}
	set<pii> S[3];
	for(int i=0; i<kto.size(); i++){
		S[i].insert(mp(1, kto[i]));
		typ[kto[i]]=i;
	}
	typ[cent]=-1;
	for(int i=0; i<n; i++){
		if(dep[i]>1){
			if(attractionsBehind(i, kto[0])*2>n){
				S[0].insert(mp(dep[i], i));
				typ[i]=0;
			}
			else if(attractionsBehind(i, kto[1])*2>n){
				S[1].insert(mp(dep[i], i));
				typ[i]=1;
			}
			else{
				S[2].insert(mp(dep[i], i));
				typ[i]=2;
			}
		}
	}
	vi ans;
	int lst=0, opt=S[0].crbegin()->st;
	for(int i=1; i<kto.size(); i++)if(opt<S[i].crbegin()->st){
		lst=i;
		opt=S[i].crbegin()->st;
	}
	ans.pb(S[lst].crbegin()->nd);
	S[lst].erase(--S[lst].end());
	while(max({S[0].size(), S[1].size(), S[2].size()})*2<S[0].size()+S[1].size()+S[2].size()){
		int akt=(lst+1)%3;
		opt=S[akt].crbegin()->st;
		if(opt<S[(akt+1)%3].crbegin()->st){
			akt=(akt+1)%3;
			opt=S[(akt+1)%3].crbegin()->st;
		}
		lst=akt;
		ans.pb(S[lst].crbegin()->nd);
		S[lst].erase(--S[lst].end());
	}
	if(S[0].size()<S[1].size()){
		swap(S[0], S[1]);
		if(lst==0 || lst==1)lst^=1;
	}
	if(S[0].size()<S[2].size()){
		swap(S[0], S[2]);
		if(lst==0 || lst==2)lst^=2;
	}
	if(lst!=0 && S[lst^3].size() && S[lst^3].crbegin()->st>dep[ans.back()]){
		ans.pb(S[lst^3].crbegin()->nd);
		S[lst^3].erase(--S[lst^3].end());
		lst^=3;
	}
	for(auto i:S[2]){
		S[1].insert(i);
	}
	if(S[0].size()>S[1].size())S[1].insert(mp(0, cent));
	else if(S[0].size()<S[1].size())S[0].insert(mp(0, cent));
	else if(lst==0)S[1].insert(mp(0, cent));
	else S[0].insert(mp(0, cent));
	lst=min(lst, 1);
	while(ans.size()<n){
		lst^=1;
		ans.pb(S[lst].crbegin()->nd);
		S[lst].erase(--S[lst].end());
	}
	for(int i=1; i<n; i++){
		//deb(ans[i], ans[i-1], hoursRequired(ans[i], ans[i-1]))
	}
	for(int i:ans){
		//cerr<<i<<" ";
	}
	return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:46:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0; i<kto.size(); i++){
      |               ~^~~~~~~~~~~
fun.cpp:69:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i=1; i<kto.size(); i++)if(opt<S[i].crbegin()->st){
      |               ~^~~~~~~~~~~
fun.cpp:107:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |  while(ans.size()<n){
      |        ~~~~~~~~~~^~
fun.cpp:115:10: warning: unused variable 'i' [-Wunused-variable]
  115 |  for(int i:ans){
      |          ^

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