Submission #741743

#	Time	Username	Problem	Language	Result	Execution time	Memory
741743		myrcella	Fun Tour (APIO20_fun)	C++17	100 / 100	260 ms	23500 KiB

fun

//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
#include "fun.h"
 
const int maxn = 1e5+10;
 
int n;
int val[maxn];
int dis[maxn];
vector <int> rt;
vector <pii> node[3];
 
vector <int> solve(vector<vector <pii> > nodee) {
		vector <int> ans;
	  int cur = 0;
	  if (SZ(nodee[1])>SZ(nodee[0])) cur = 1;
	  while (!nodee[cur].empty()) {
		  ans.pb(nodee[cur].back().se);
		  nodee[cur].pop_back();
		  cur ^= 1;
	  }
	  return ans;
}
 
std::vector<int> createFunTour(int N, int Q) {
	if (N==2) {
		vector <int> tmp = {0,1};
		return tmp;
	}
	int cent = -1;
	n = N;
  rep(i,0,n) {
	  val[i] = attractionsBehind(0,i);
	  if (val[i]*2>=N) 
		  if (cent==-1 or val[i]<val[cent]) cent=i;
  }
  rep(i,0,n) if (cent!=i) {
	  dis[i] = hoursRequired(cent,i);
	  if (dis[i]==1) rt.pb(i);
  }
  rep(i,0,n) if (cent!=i) {
	  bool ok = false;
	  rep(j,0,SZ(rt)-1) if (hoursRequired(rt[j],i)+1==dis[i]) {
		  ok = true;
		  node[j].pb({dis[i],i});
		  break;
	  }
	  if (ok==false) node[SZ(rt)-1].pb({dis[i],i});
  }
  sort(ALL(node[0]));sort(ALL(node[1]));
  vector <int> ans;
 // debug(cent);
  //for (auto it:node[1]) debug(it.se);
  if (SZ(rt)==2) {
	  ans = solve({node[0],node[1]});
  }
  else {
	  sort(ALL(node[2]));
	  bool ok = false;
	  int lst,lstrt = -1;
	  rep(i,0,3) {
			  if (SZ(node[i])>=SZ(node[0])+SZ(node[1])+SZ(node[2]) - SZ(node[i])) {
				  vector <pii> small;
				  rep(j,0,3) if (i!=j) while (!node[j].empty()) small.pb(node[j].back()),node[j].pop_back();
				  sort(ALL(small));
				  vector <int> hmm = solve({small,node[i]});
				  for (auto it:hmm) ans.pb(it);
				  ok = true;
				  break;
			  }
		  }
	  if (ok==false) while (1) {
		  int tmp = -1;
		  if (lstrt!=0 and (tmp==-1 or node[1].back().fi > node[tmp].back().fi)) tmp = 0;
		  if (lstrt!=1 and (tmp==-1 or node[1].back().fi > node[tmp].back().fi)) tmp = 1;
		  if (lstrt!=2 and (tmp==-1 or node[2].back().fi > node[tmp].back().fi)) tmp = 2;
		  ans.pb(node[tmp].back().se);
		  lst = node[tmp].back().fi;
		  lstrt = tmp;
		  node[tmp].pop_back();
		  ok = false;
		  rep(i,0,3) {
			  if (SZ(node[i])==SZ(node[0])+SZ(node[1])+SZ(node[2]) - SZ(node[i])) {
				  vector <pii> small;
				  rep(j,0,3) if (i!=j) while (!node[j].empty()) small.pb(node[j].back()),node[j].pop_back();
				  sort(ALL(small));
				  if (small.back().fi>lst) {
					  ans.pb(small.back().se);
					  small.pop_back();
				  }
				  vector <int> hmm = solve({node[i],small});
				  for (auto it:hmm) ans.pb(it);
				  ok = true;
				  break;
			  }
		  }
		  if (ok) break;
	  }
  }
  ans.pb(cent);
  
  return ans;
}

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