Submission #1192608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192608		catch_me_if_you_can	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	9 ms	428 KiB

longesttrip

#include<bits/stdc++.h>
#include "longesttrip.h"

using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back

bool c_edge(int u, int v)
{
	return are_connected({u}, {v});
}

vector<int> longest_trip(int n, int d)
{
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<int> v1;
	vector<int> v2;
	bool enemy = false;
	vector<int> SSS(n);
	for(int i = 0; i < n; i++)
		SSS[i] = i;
	shuffle(SSS.begin(), SSS.end(), rng);
	for(int Sr = 0; Sr < n; Sr++)
	{
		int i = SSS[Sr];
		if(v1.size() < v2.size())
			swap(v1, v2);
		if(v1.empty())
		{
			v1.pb(i);
			continue;
		}
		if(v2.empty())
		{
			v2.pb(i);
			continue;
		}
		if(c_edge(v1.back(), i))
		{
			v1.pb(i);
			enemy = false;
			continue;
		}
		else if(enemy)
		{
			v2.pb(i);
			continue;
		}
		if(c_edge(v2.back(), i))
		{
			v2.pb(i);
			enemy = true;
			continue;
		}
		while(v1.size())
		{
			v2.pb(v1.back());
			v1.pob();
		}
		v1.pb(i);
		enemy = false;
	}
	if(c_edge(v1.back(), v2.back()))
	{
		while(v1.size())
		{
			v2.pb(v1.back());
			v1.pob();
		}
		return v2;
	}
	if(c_edge(v1.front(), v2.back()))
	{
		reverse(v1.begin(), v1.end());
		while(v1.size())
		{
			v2.pb(v1.back());
			v1.pob();
		}
		return v2;
	}
	reverse(v2.begin(), v2.end());
	if(c_edge(v1.back(), v2.back()))
	{
		while(v1.size())
		{
			v2.pb(v1.back());
			v1.pob();
		}
		return v2;
	}
	if(c_edge(v1.front(), v2.back()))
	{
		reverse(v1.begin(), v1.end());
		while(v1.size())
		{
			v2.pb(v1.back());
			v1.pob();
		}
		return v2;
	}
	if(v1.empty())
		return v2;
	if(v2.empty())
		return v1;
	if(v1.size() > v2.size())
		swap(v1, v2);
	if(!are_connected(v1, v2))
		return v2;
	int l = 0;
	int r = v2.size()-1;
	while(l < r)
	{
		int m = (l+r)/2;
		vector<int> s = v2;
		s.resize(m+1);
		if(are_connected(v1, s))
			r = m;
		else
			l = m+1;
	}
	int S2 = l;//v2[S] is target.
	l = 0;
	r = v1.size()-1;
	while(l < r)
	{
		int m = (l+r)/2;
		vector<int> s = v1;
		s.resize(m+1);
		if(are_connected({v2[S2]}, s))
			r = m;
		else
			l = m+1;
	}
	int S1 = l; //v1[S1], v2[S2] are connected.
	//(n-1-S1)
	vector<int> pth;
	for(int i = S1-1; i >= 0; i--)
		pth.pb(v1[i]);
	for(int i = v1.size()-1; i >= S1; i--)
		pth.pb(v1[i]);
	for(int i = S2; i < v2.size(); i++)
		pth.pb(v2[i]);
	for(int i = 0; i < S2; i++)
		pth.pb(v2[i]);
	return pth;
}

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