Submission #852649

#	Time	Username	Problem	Language	Result	Execution time	Memory
852649		aZvezda	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	15 ms	856 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

vector<int> longest_trip(int N, int D) {
	vector<int> p1, p2;
	p1.push_back(N - 1);
	if (N % 2 == 0) {
		if (are_connected({N - 2}, {N - 1})) {
			p1.push_back(N - 2);
		} else {
			p2.push_back(N - 2);
		}
	}
	for (int i = 0; i < N - 2; i += 2) {
		if (sz(p2) == 0) {
			bool v1 = are_connected({i}, {i + 1});
			bool v2 = are_connected({p1.back()}, {i});
			bool v3 = are_connected({p1.back()}, {i + 1});
			if (v1) {
				if (v2) {
					p1.push_back(i);
					p1.push_back(i + 1);
				} else if (v3) {
					p1.push_back(i + 1);
					p1.push_back(i);
				} else {
					p2.push_back(i);
					p2.push_back(i + 1);
				}
			} else {
				if (v2) {
					p1.push_back(i);
					p2.push_back(i + 1);
				} else {
					p2.push_back(i);
					p1.push_back(i + 1);
				}
			}
		} else {
			int v = i, w = i + 1;
			bool v1 = are_connected({v}, {w});
			if (v1) {
				if (!are_connected({p1.back()}, {v}))
					swap(p1, p2);
				if (are_connected({p2.back()}, {w})) {
					p1.push_back(v);
					p1.push_back(w);
					for (int i = sz(p2) - 1; i >= 0; i--)
						p1.push_back(p2[i]);
					p2.clear();
				} else {
					p1.push_back(v);
					p1.push_back(w);
				}
			} else {
				if (!are_connected({p1.back()}, {v}))
					swap(p1, p2);
				if (are_connected({p2.back()}, {w})) {
					p1.push_back(v);
					p2.push_back(w);
				} else {
					p1.push_back(w);
					p2.push_back(v);
				}
			}
		}
	}
	if (sz(p1) < sz(p2))
		swap(p1, p2);
	if (sz(p2) == 0)
		return p1;
	if (!are_connected(p1, p2)) {
		return p1;
	}
	if ((sz(p1) <= 2 || are_connected({p1.front()}, {p1.back()})) && (sz(p2) <= 2 || are_connected({p2.front()}, {p2.back()}))) {
		int s1 = 0, e1 = sz(p1);
		int s2 = 0, e2 = sz(p2);
		while (e2 - s2 > 1) {
			int m2 = (s2 + e2) / 2;
			vector<int> q(p2.begin() + s2, p2.begin() + m2);
			if (are_connected(p1, q))
				e2 = m2;
			else
				s2 = m2;
		}
		while (e1 - s1 > 1) {
			int m1 = (s1 + e1) / 2;
			vector<int> q(p1.begin() + s1, p1.begin() + m1);
			if (are_connected(q, {p2[s2]}))
				e1 = m1;
			else
				s1 = m1;
		}
		rotate(p1.begin(), p1.begin() + s1, p1.end());
		rotate(p2.begin(), p2.begin() + s2, p2.end());
		reverse(all(p2));
		for (auto &x : p1)
			p2.push_back(x);
		return p2;
	}
	if (are_connected({p1[0]}, {p2[0]})) {
		reverse(all(p2));
		for (auto &x : p1)
			p2.push_back(x);
		return p2;
	}
	if (are_connected({p1[0]}, {p2.back()})) {
		for (auto &x : p1)
			p2.push_back(x);
		return p2;
	}
	if (are_connected({p1.back()}, {p2[0]})) {
		for (auto &x : p2)
			p1.push_back(x);
		return p1;
	}
	if (are_connected({p1.back()}, {p2.back()})) {
		reverse(all(p2));
		for (auto &x : p2)
			p1.push_back(x);
		return p1;
	}
	assert(0);
}

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