Submission #1109676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109676		jerzyk	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	40 ms	848 KiB

longesttrip

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const int N = 1000 * 1000 + 7;

bool SQ(int a, int b)
{
	vector<int> v1 = {a}, v2 = {b};
	return are_connected(v1, v2);
}

void J(vector<int> &a, vector<int> &b)
{
	for(int i = 0; i < (int)b.size(); ++i)
		a.pb(b[i]);
	b.clear();
}

void R(vector<int> &a, int r)
{
	vector<int> nw;
	for(int i = r; i < (int)a.size(); ++i)
		nw.pb(a[i]);
	for(int i = 0; i < r; ++i)
		nw.pb(a[i]);
	a = nw;
}

void Merge(vector<int> &a, vector<int> &b, bool xd)
{
	if(!xd && SQ(a.back(), b.back()))
	{
		reverse(b.begin(), b.end());
		J(a, b);
		return;
	}
	if(SQ(a.back(), b[0]))
	{
		J(a, b);
		return;
	}
	if(SQ(a[0], b.back()))
	{
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		J(a, b);
		return;
	}

	int p, s, k;
	vector<int> q1, qd;
	p = 0, k = (int)a.size();
	while(p < k)
	{
		s = (p + k) / 2;
		q1.clear();
		for(int i = 0; i <= s; ++i)
			q1.pb(a[i]);
		if(are_connected(q1, b))
			k = s;
		else
			p = s + 1;
	}
	if(p == (int)a.size()) return;

	R(a, p);
	qd = {a[0]};
	p = 0, k = (int)b.size();
	while(p < k)
	{
		s = (p + k) / 2;
		q1.clear();
		for(int i = 0; i <= s; ++i)
			q1.pb(b[i]);
		if(are_connected(q1, qd))
			k = s;
		else
			p = s + 1;
	}
	R(b, p);
	reverse(a.begin(), a.end());
	J(a, b);
}

vector<int> longest_trip(int _N, int _X_D)
{
	int n = _N;
	vector<int> l1, l2;
	bool xd = true;
	l1.pb(0);

	for(int i = 1; i < n; ++i)
	{
		if(l1.size() < l2.size()) swap(l1, l2);

		if(SQ(i, l1.back()))
		{
			l1.pb(i);
			if(l2.size() != 0) xd = false;
			continue;
		}
		if(xd || SQ(i, l2.back()))
		{
			l2.pb(i);
			xd = true;
			continue;
		}
		reverse(l2.begin(), l2.end());
		if((int)l2.size() > 0) xd = false;
		else xd = true;
		J(l1, l2);
		l2.pb(i);
	}
	if(n == 1) return l1;

	
	if(l1.size() < l2.size())
		swap(l1, l2);
	if(l2.size() == 0)
		return l1;
	Merge(l1, l2, xd);
	return l1;
}

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