Submission #1010948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010948		thangdz2k7	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	11 ms	696 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vec;
#define q are_connected
#define pb push_back
vec a, b; int p[256];
void app() {
	for (int i : b) a. pb(i);
	b. clear();
}
vec longest_trip(int n, int d) {
	srand(114);
	for (int i=0; i<n; i++) p[i] = i;
	random_shuffle (p, p+n);
	a = vec {p[0]}, b = vec {p[1]};
	bool f = 0;
	for (int _=2; _<n; _++) {
		int i = p[_];
		if (q({a. back()}, {i})) a. pb(i), f = 0;
		else if (f || q({b. back()}, {i})) b. pb(i), f = 1;
		else reverse (b. begin(), b. end()), app(), b. pb(i);
	}
	if (b. empty()) return a;
	if (! q(a, b)) return a. size() > b. size() ? a : b;
	if (! f && q({a. back()}, {b. back()})) return reverse (b. begin(), b. end()), app(), a;
	if (q({a. back()}, b)) {
		int l = 0, r = b. size() - 2;
		while (l < r) {
			int mid = l + r >> 1;
			if (q({a. back()}, vec (b. begin(), b. begin() + mid + 1))) r = mid;
			else l = mid + 1;
		} return rotate (b. begin(), b. begin() + r, b. end()), app(), a;
	} else {
		int l = 0, r = a. size() - 2;
		while (l < r) {
			int mid = l + r >> 1;
			if (q(vec (a. begin(), a. begin() + mid + 1), b)) r = mid;
			else l = mid + 1;
		} r ? rotate (a. begin(), a. begin() + r + 1, a. end()), void () : reverse (a. begin(), a. end());
		l = 0, r = b. size() - 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (q({a. back()}, vec (b. begin(), b. begin() + mid + 1))) r = mid;
			else l = mid + 1;
		} return rotate (b. begin(), b. begin() + r, b. end()), app(), a;
	}
}

Compilation message (stderr)

longesttrip.cpp: In function 'vec longest_trip(int, int)':
longesttrip.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |    int mid = l + r >> 1;
      |              ~~^~~
longesttrip.cpp:37:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |    int mid = l + r >> 1;
      |              ~~^~~
longesttrip.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |    int mid = l + r >> 1;
      |              ~~^~~

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