Submission #1040250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040250		Rafi22	Fun Tour (APIO20_fun)	C++14	100 / 100	129 ms	22956 KiB

fun

    #include "fun.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    #ifdef DEBUG
    auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
    auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
    #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
    #else
    #define debug(...){}
    #endif
     
    #define ll long long
    #define ld long double
    #define endl '\n'
    #define st first
    #define nd second
    #define pb push_back
    #define sz(x) (int)(x).size()
    #define all(x) (x).begin(), (x).end()
    #define FOR(i,l,r) for(int i=(l);i<=(r);i++)
    #define ROF(i,r,l) for(int i=(r);i>=(l);i--)
    int inf=1000000007;
    ll infl=1000000000000000007;
    ll mod=1000000007;
     
    const int N=100007;
     
    int d[N];
    int s[N];
    int id[N];
    vector<pair<int,int>>X[3];
     
    vector<int>createFunTour(int n,int q)
    {
    	int C=-1,mn=inf;
    	FOR(i,0,n-1) 
    	{
    		s[i]=attractionsBehind(0,i);
    		if(s[i]>=(n+1)/2&&s[i]<mn)
    		{
    			mn=s[i];
    			C=i;
    		}
    	}
    	vector<pair<int,int>>V;
    	FOR(i,0,n-1)
    	{
    		d[i]=hoursRequired(C,i);
    		if(d[i]==1) 
    		{
    			if(s[i]>s[C]) V.pb({i,n-s[C]});
    			else V.pb({i,s[i]});
    		}
    	}
    	debug(C,V);
    	vector<int>ans;
    	FOR(i,0,n-1)
    	{
    		if(i==C) continue;
    		if(V[0].st==i||attractionsBehind(i,V[0].st)>=n-V[0].nd+1)id[i]=0;
    		else if(V[1].st==i||attractionsBehind(i,V[1].st)>=n-V[1].nd+1) id[i]=1;
    		else id[i]=2;
    		//debug(id[i],i);
    		X[id[i]].pb({d[i],i});
    	}
    	FOR(i,0,2) sort(all(X[i]));
    	int last=-1;
    	FOR(i,1,n-1)
    	{
    		int m=n-i;
    		int mx=-1,f=-1,xd=-1;
    		FOR(j,0,2)
    		{
    			if(j==last) continue;
    			if(sz(X[j])==(m+1)/2)
    			{
					bool nie=0;
					int D=0;
					FOR(l,0,2) if(l!=j&&sz(X[l])>0) D=max(D,X[l].back().st);
					if(sz(ans)>0&&d[ans.back()]<D) nie=1;
					if(!nie) xd=j;
				}
    			if(sz(X[j])>0&&X[j].back().st>mx)
    			{
    				mx=X[j].back().st;
    				f=j;
    			}
    		}
    		if(xd!=-1)
    		{
    			vector<pair<int,int>>A=X[xd],B;
    			FOR(j,0,2) if(j!=xd) for(auto p:X[j]) B.pb(p);
    			sort(all(A));
    			sort(all(B));
    			FOR(i,0,m-1) 
    			{
    				if(i%2==0)
    				{
    					ans.pb(A.back().nd);
    					A.pop_back();
    				}
    				else
    				{
    					ans.pb(B.back().nd);
    					B.pop_back();
    				}
    			}
    			break;
    		}
    		if(f==-1) exit(2137);
    		ans.pb(X[f].back().nd);
    		X[f].pop_back();
    		last=f;
    	}
    	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