제출 #1313005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313005		Jawad_Akbar_JJ	Longest Trip (IOI23_longesttrip)	C++20	85 / 100	7 ms	440 KiB

longesttrip

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

#include "longesttrip.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int get(vector<int> A, vector<int> B){
	int l = -1, r = A.size() - 1;
	while (l + 1 < r){
		int m = (l + r) / 2;
		vector<int> v;
		v.insert(v.end(), A.begin(), A.begin() + m + 1);
		if (are_connected(v, B))
			r = m;
		else
			l = m;
	}
	return r;
}

vector<int> longest_trip(int n, int D){
	vector<int> A, B, v;
	for (int i=0;i<n;i++)
		v.push_back(i);
	shuffle(begin(v), end(v), rng);
	for (int i : v){
		if (A.size() == 0 or are_connected({A.back()}, {i})){
			A.push_back(i);
		}
		else{
			if (B.size() > 0 and are_connected({A.back()}, {B.back()})){
				reverse(begin(B), end(B));
				A.insert(A.end(), B.begin(), B.end());
				B.clear();
			}
			B.push_back(i);
		}
		if (A.size() < B.size())
			swap(A, B);
	}

	if (B.size() == 0 or are_connected(A, B) == 0)
		return A;

	int l1 = get(A, B), l2 = get(B, {A[l1]});
	if (l2 == 0)
		swap(A, B), swap(l1, l2);

	if (l1){
		for (int i=1;i<=l1;i++)
			A.push_back(A[0]), A.erase(begin(A));
		for (int i=1;i<=l2;i++)
			B.push_back(B[0]), B.erase(begin(B));
	}
	else if (are_connected({A[0]}, {B.back()})){
		reverse(begin(B), end(B));
	}
	else{
		for (int i=1;i<=l2;i++)
			B.push_back(B[0]), B.erase(begin(B));
	}

	for (int i : B)
		A.insert(A.begin(), i);
	return A;
}

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