제출 #1256383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256383		flappybird	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	7 ms	416 KiB

longesttrip

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

vector<int> longest_trip(int N, int D) {
	vector<int> v1, v2;
	int i;
	vector<int> rems;
	for (i = 1; i < N; i++) rems.push_back(i);
	v1.push_back(0);
	while (rems.size()) {
		int x, y;
		if (rems.size() == 1) {
			x = rems.back();
			rems.pop_back();

			if (v2.empty()) {
				int a = v1.back();
				if (are_connected({ a }, { x })) v1.push_back(x);
				else v2.push_back(x);
			}
			else {
				int a = v1.back();
				int b = v2.back();
				auto c1 = are_connected({ x }, { a });
				auto c2 = are_connected({ x }, { b });
				if (c1 && c2) {
					v1.push_back(x);
					while (v2.size()) v1.push_back(v2.back()), v2.pop_back();
				}
				else if (c1) v1.push_back(x);
				else if (c2) v2.push_back(x);
				else assert(0);
			}
		}
		else {
			x = rems.back();
			rems.pop_back();
			y = rems.back();
			rems.pop_back();
			if (v2.empty()) {
				int a = v1.back();
				auto ax = are_connected({ a }, { x });
				auto ay = are_connected({ a }, { y });
				auto xy = are_connected({ x }, { y });
				if (ax && xy) {
					v1.push_back(x);
					v1.push_back(y);
				}
				else if (ay && xy) {
					v1.push_back(y);
					v1.push_back(x);
				}
				else if (ax) {
					v1.push_back(x);
					v2.push_back(y);
				}
				else if (ay) {
					v1.push_back(y);
					v2.push_back(x);
				}
				else {
					assert(xy);
					v2.push_back(x);
					v2.push_back(y);
				}
			}
			else {
				int a = v1.back();
				int b = v2.back();
				if (are_connected({ x }, { y })) {
					if (are_connected({ a }, { x })) {
						if (are_connected({ b }, { y })) {
							v1.push_back(x);
							v1.push_back(y);
							while (v2.size()) v1.push_back(v2.back()), v2.pop_back();
						}
						else {
							v1.push_back(x);
							v1.push_back(y);
						}
					}
					else {
						if (are_connected({ a }, { y })) {
							v1.push_back(y);
							v1.push_back(x);
							while (v2.size()) v1.push_back(v2.back()), v2.pop_back();
						}
						else {
							v2.push_back(x);
							v2.push_back(y);
						}
					}
				}
				else {
					if (are_connected({ a }, { x })) {
						if (are_connected({ b }, { y })) {
							v1.push_back(x);
							v2.push_back(y);
						}
						else {
							v1.push_back(y);
							v2.push_back(x);
						}
					}
					else {
						v1.push_back(y);
						v2.push_back(x);
					}
				}
			}
		}
		if (v1.size() && v2.size()) assert(!are_connected({ v1.back() }, { v2.back() }));
	}

	for (i = 1; i < v1.size(); i++) {
		assert(are_connected({ v1[i - 1] }, { v1[i] }));
	}
	for (i = 1; i < v2.size(); i++) {
		assert(are_connected({ v2[i - 1] }, { v2[i] }));
	}

	if (v2.empty()) return v1;

	if (!are_connected(v1, v2)) {
		if (v1.size() < v2.size()) return v2;
		else return v1;
	}

	int M, K;
	M = v1.size();
	K = v2.size();

	int l, r;
	l = -1;
	r = M - 1;
	while (r - l > 1) {
		int m = l + r >> 1;
		vector<int> prf = v1;
		prf.resize(m + 1);
		if (are_connected(prf, v2)) r = m;
		else l = m;
	}

	int u = r;
	vector<int> v1prf = v1;
	v1prf.resize(r + 1);

	assert(are_connected(v1prf, v2));

	l = -1;
	r = K - 1;
	while (r - l > 1) {
		int m = l + r >> 1;
		vector<int> prf = v2;
		prf.resize(m + 1);
		if (are_connected(v1prf, prf)) r = m;
		else l = m;
	}
	int v = r;

	assert(are_connected({ v1[u] }, { v2[v] }));

	vector<int> allv;
	int st = (u + 1) % M;
	for (i = 0; i < M; i++) {
		allv.push_back(v1[st]);
		st = (st + 1) % M;
	}

	st = v;
	for (i = 0; i < K; i++) {
		allv.push_back(v2[st]);
		st = (st + 1) % K;
	}
	return allv;
}

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