Submission #1233708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233708		nikulid	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	4 ms	396 KiB

longesttrip

#include "longesttrip.h"
#include <queue>

using namespace std;

#define pb push_back

vector<int> longest_trip(int n, int d){
	vector<int> ans;
	if(d==2){
		// surely there still exists a round trip...
		// why is this screaming linked list :(
		vector<int> starts;
		if(!are_connected({0}, {n-1})){
			starts.pb(0);
		}
		for(int i=1; i<n; i++){
			if(!are_connected({i-1}, {i})){
				starts.pb(i);
			}
		}
		if(starts.size()==0){
			d=3; // go do the easy case (0,1,2,...)
		} else{
			// we certainly have breaks somewhere.
			starts.pb(starts[0]+n);
			bool forwards=false;
			for(int j=0; j<starts.size()-1; j++){				
				forwards = !forwards;
				if(forwards){
					// forwards
					for(int i=starts[j]; i<starts[j+1]; i++){
						ans.pb(i%n);
					}
				} else{
					// backwards
					for(int i=starts[j+1]-1; i>starts[j]-1; i--){
						ans.pb(i%n);
					}
				}
			}
		}

	}
	if(d==3){
		for(int i=0; i<n; i++){
			ans.pb(i);
		}
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60