Submission #566822

#	Time	Username	Problem	Language	Result	Execution time	Memory
566822		zaneyu	Fun Tour (APIO20_fun)	C++14	100 / 100	257 ms	23748 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pii pair<int,int>
#define s second
#define MNTO(x,y) x=min(x,y)
#define ALL(x) x.begin(),x.end()
using namespace std;
const int maxn=1e5+5;
#define REP(i,n) for(int i=0;i<n;i++)
int d[maxn],p[maxn];
vector<int> t[maxn];
bool cmp(int a,int b){
	return d[a]<d[b];
}
bool cmp2(int a,int b){
	return sz(t[a])>sz(t[b]);
}
bool cmp3(int a,int b){
	return d[t[a].back()]>d[t[b].back()];
}
vector<int> createFunTour(int n, int q) {
	pii mn={INT_MAX,-1};
	REP(i,n){
		int sz=attractionsBehind(0,i);
		if(sz>n/2) MNTO(mn,make_pair(sz,i));
	}
	int c=mn.s;
	vector<int> v;
	REP(i,n){
		d[i]=hoursRequired(c,i);
		if(d[i]==1) v.pb(i);
	}
	REP(i,n){
		if(i==c) continue;
		while(p[i]<sz(v)-1 and hoursRequired(v[p[i]],i)>d[i]) ++p[i];
		t[p[i]].pb(i);
	}
	int ord[3]={0,1,2};
	REP(i,3) sort(ALL(t[i]),cmp);
	sort(ord,ord+3,cmp2);
	vector<int> ans;
	int pv=-1;
	while(sz(t[ord[0]])<sz(t[ord[1]])+sz(t[ord[2]])){
		sort(ord,ord+3,cmp3);
		int i=(pv==ord[0]);
		ans.pb(t[ord[i]].back());
		t[ord[i]].pop_back();
		pv=ord[i];
		sort(ord,ord+3,cmp2);
	}
	t[ord[1]].insert(t[ord[1]].end(),ALL(t[ord[2]]));
	sort(ALL(t[ord[1]]),cmp);
	int st=0;
	if(sz(ans)>1 and d[ans.back()]<d[t[ord[1]].back()]) st=1;
	while(sz(t[ord[st]])){
		ans.pb(t[ord[st]].back());
		t[ord[st]].pop_back();
		st=1-st;
	}
	ans.pb(c);
	return ans;
}

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