Submission #841788

#	Time	Username	Problem	Language	Result	Execution time	Memory
841788		emuyumi	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	59 ms	1500 KiB

longesttrip

#include "longesttrip.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> longest_trip(int N, int D) {

	if (D >= 2) {
		set<int> s;
		for (int i = 1; i < N; ++i) {
			s.insert(i);
		}
		vector<int> ans = {0};
		while (!s.empty()) {
			int v = ans.back();
			bool found = 0;
			for (int to : s) {
				bool b = are_connected({v}, {to});
				if (b) {
					s.erase(to);
					ans.push_back(to);
					found = 1;
					break;
				}
			}
			if (!found) {
				int last = *s.begin();
				ans.insert(ans.begin(), last);
				break;
			}
		}
		return ans;
	}

	// if (N == 3) {
	// 	int cnt = 0;
	// 	int x = 0;
	// 	auto go = [&](int i, int j) {
	// 		if (are_connected({i}, {j})) {
	// 			cnt++;
	// 			x ^= i;
	// 			x ^= j;
	// 		}
	// 	};
	// 	go(0, 1);
	// 	go(0, 2);
	// 	go(1, 2);
	// 	if (cnt == 0) return {0};
	// 	int other = 3^x;
	// 	set<int> s = {0, 1, 2};
	// 	s.erase(other);
	// 	int v1 = *s.begin();
	// 	int v2 = *(++s.begin());
	// 	if (cnt == 1) {
	// 		return {v1, v2};
	// 	}
	// 	return {v1, other, v2};
	// }

	// check if single component
	// if not, each component is clique, problem is then find largest component

	// otherwise, one component,
	// start with one node and keep trying to extend path by randomly querying
	// if gets stuck, that means past must be a clique, done

	int calls = 0;
	auto my_are_connected = [&](vector<int> a, vector<int> b) {
		calls ++;
		assert(calls <= 32460);
		return are_connected(a, b);
	};

	bool found = 0;
	vector<int> answer;
	using vi = vector<int>;
	auto halves = [&](vector<int> v) -> pair<vi, vi> {
		int m = v.size() / 2;
		return {{v.begin(), v.begin()+m}, {v.begin()+m, v.end()}};
	};

	vector<int> path = {0};
	vector<int> left(N-1);
	iota(left.begin(), left.end(), 1);
	while (left.size()) {
		random_shuffle(left.begin(), left.end());

		// cout << "! ";
		// for (int x : left) {
		// 	cout << x << " ";
		// }
		// cout << '\n';

		auto locate = [&](vector<int> src, vector<int> dest) -> int {
			while (src.size() != 1) {
				auto [a, b] = halves(src);
				if (my_are_connected(a, dest)) src = a;
				else src = b;
			}
			return src[0];
		};

		int v = path.back();
		int nxt = locate(left, {v});
		if (!my_are_connected({nxt}, {v})) {

			if (!my_are_connected(path, left)) {
				if (path.size() > left.size()) return path;
				else return left;
			}
			int a = locate(path, left);
			int b = locate(left, {a});

			vector<int> ans = left;
			ans.erase(find(ans.begin(), ans.end(), b));
			ans.push_back(b);
			int j = find(path.begin(), path.end(), a) - path.begin();
			if (j == 0) {
				for (int x : path) {
					ans.push_back(x);
				}
			}
			else {
				for (int i = j; i >= 0; --i) {
					ans.push_back(path[i]);
				}
				for (int i = path.size()-1; i > j; --i) {
					ans.push_back(path[i]);
				}
			}
			for (int i = 1; i < ans.size(); ++i) {
				assert(my_are_connected({ans[i]}, {ans[i-1]}));
			}
			return ans;

			// path.erase(find(path.begin(), path.end(), a));
			// left.erase(find(left.begin(), left.end(), b));
			// path.push_back(a);
			// left.insert(left.begin(), a);
			// for (int x : left) path.push_back(x);
			// return path;
			// int lst = end(path)[-2];
			// vector<int> ans = {v, lst};
			// for (int i = 0; i < N; ++i) {
			// 	if (i != v && i != lst) ans.push_back(i);
			// }
			// for (int i = 1; i < ans.size(); ++i) {
			// 	assert(my_are_connected({ans[i]}, {ans[i-1]}));
			// }
			// return ans;
		}
		else {
			path.push_back(nxt);
			left.erase(find(left.begin(), left.end(), nxt));
		}
	}
	for (int i = 1; i < path.size(); ++i) {
		assert(my_are_connected({path[i]}, {path[i-1]}));
	}
	return path;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |    for (int i = 1; i < ans.size(); ++i) {
      |                    ~~^~~~~~~~~~~~
longesttrip.cpp:158:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |  for (int i = 1; i < path.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
longesttrip.cpp:75:7: warning: unused variable 'found' [-Wunused-variable]
   75 |  bool found = 0;
      |       ^~~~~

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