Submission #1242160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242160		AmirAli_H1	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	5 ms	424 KiB

longesttrip

// In the name of Allah

#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 10) + 4;

int n;
vector<int> ls1, ls2, lsx;
vector<int> A1, A2;

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

void addx(int v1, int v2) {
	if (askx(v1, v2)) {
		if (len(ls1) == 0) {
			ls1.pb(v1); ls1.pb(v2);
			return ;
		}
		else if (len(ls2) == 0) {
			if (askx(ls1.back(), v1)) {
				ls1.pb(v1); ls1.pb(v2);
				return ;
			}
			else {
				ls2.pb(v2); ls2.pb(v1);
				return ;
			}
		}
		if (askx(ls1.back(), v1)) {
			if (!askx(ls2.back(), v2)) {
				ls1.pb(v1); ls1.pb(v2);
				return ;
			}
			else {
				ls1.pb(v1); ls1.pb(v2); reverse(all(ls2));
				for (int x : ls2) ls1.pb(x);
				ls2.clear();
			}
		}
		else {
			if (!askx(ls1.back(), v2)) {
				ls2.pb(v1); ls2.pb(v2);
				return ;
			}
			else {
				ls2.pb(v1); ls2.pb(v2); reverse(all(ls1));
				for (int x : ls1) ls2.pb(x);
				ls1.clear(); ls1.swap(ls2);
			}
		}
	}
	else {
		if (len(ls1) == 0) {
			ls1.pb(v1); ls2.pb(v2);
			return ;
		}
		else if (len(ls2) == 0) {
			if (askx(ls1.back(), v1)) {
				ls1.pb(v1); ls2.pb(v2);
				return ;
			}
			else {
				ls1.pb(v2); ls2.pb(v1);
				return ;
			}
		}
		if (!askx(ls1.back(), v1)) {
			ls2.pb(v1); ls1.pb(v2);
			return ;
		}
		else {
			if (askx(ls2.back(), v2)) {
				ls1.pb(v1); ls2.pb(v2);
				return ;
			}
			else {
				ls2.pb(v1); ls1.pb(v2);
				return ;
			}
		}
	}
}

void addw(int v1) {
	if (len(ls2) == 0) {
		if (askx(ls1.back(), v1)) ls1.pb(v1);
		else ls2.pb(v1);
		return ;
	}
	if (!askx(ls1.back(), v1)) ls2.pb(v1);
	else if (!askx(ls2.back(), v1)) ls1.pb(v1);
	else {
		ls1.pb(v1); reverse(all(ls2));
		for (int x : ls2) ls1.pb(x);
		ls2.clear();
	}
}

bool okx(int l1, int r1, int l2, int r2) {
	A1.clear(); A2.clear();
	for (int i = l1; i < r1; i++) A1.pb(ls1[i]);
	for (int i = l2; i < r2; i++) A2.pb(ls2[i]);
	return are_connected(A1, A2);
}

vector<int> longest_trip(int N, int D) {
	n = N; ls1.clear(); ls2.clear();
	for (int i = 0; i < n; i += 2) {
		if (i + 1 < n) addx(i, i + 1);
		else addw(i);
	}
	if (len(ls2) == 0) return ls1;
	if (!are_connected(ls1, ls2)) {
		if (len(ls1) > len(ls2)) return ls1;
		else return ls2;
	}
	for (int T = 0; T < 2; T++) {
		if (ls2[0] != ls2.back() && !askx(ls2[0], ls2.back())) {
			if (askx(ls1.back(), ls2[0])) {
				for (int x : ls2) ls1.pb(x);
				ls2.clear();
				return ls1;
			}
			else {
				reverse(all(ls2));
				for (int x : ls2) ls1.pb(x);
				ls2.clear();
				return ls1;
			}
		}
		ls1.swap(ls2);
	}
	int l1 = 0, r1 = len(ls1);
	int l2 = 0, r2 = len(ls2);
	while (r1 - l1 > 1) {
		int mid = (l1 + r1) / 2;
		if (okx(l1, mid, l2, r2)) r1 = mid;
		else l1 = mid;
	}
	while (r2 - l2 > 1) {
		int mid = (l2 + r2) / 2;
		if (okx(l1, r1, l2, mid)) r2 = mid;
		else l2 = mid;
	}
	lsx.clear();
	for (int i = l1; i < l1 + len(ls1); i++) {
		lsx.pb(ls1[i % len(ls1)]);
	}
	reverse(all(lsx));
	for (int i = l2; i < l2 + len(ls2); i++) {
		lsx.pb(ls2[i % len(ls2)]);
	}
	return lsx;
}

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