제출 #1240824

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

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

int n;

ll bins(vector<int> &v, vector<int> &v1){
	ll l = -1,r = v1.size() - 1;
	while(r > l + 1){
		ll mid = l + (r - l) / 2;
		vector<int> vv;
		for(int i = 0; i <= mid; i++) vv.pb(v1[i]);
		if(are_connected(vv, v)) r = mid;
		else l = mid;
	}
	return r;
}

std::vector<int> longest_trip(int N, int D){
	n = N;
	vector<int> v[2];
	v[0].pb(0);
	v[1].pb(1);
	bool ok = false;
	for(int i = 2; i < n; i++){
		bool x = are_connected({v[0][v[0].size() - 1]}, {i});
		if(x){
			ok = false;
			v[0].pb(i);
			continue;
		}
		if(ok) v[1].pb(i);
		else{
			ok = true;
			bool y = are_connected({v[1][v[1].size() - 1]}, {i});
			if(y) v[1].pb(i);
			else{
				reverse(v[1].begin(), v[1].end());
				for(auto it : v[1]) v[0].pb(it);
				v[1].clear();
				v[1].pb(i);
			}
		}
	}
	if(!are_connected(v[0], v[1])){
		if(v[0].size() >= v[1].size()) return v[0];
		return v[1];
	}
	bool x = are_connected({v[1][v[1].size() - 1]}, {v[0][v[0].size() - 1]}),
	y = are_connected({v[1][0]}, {v[0][v[0].size() - 1]}),z = are_connected({v[1][v[1].size() - 1]}, {v[0][0]});
	if(z){
		swap(v[0], v[1]);
		y = true;
	}
	else if(x){
		reverse(v[1].begin(), v[1].end());
		y = true;
	}
	if(y){
		for(auto it : v[1]) v[0].pb(it);
		for(int i = 1; i < v[0].size(); i++) assert(are_connected({v[0][i]}, {v[0][i - 1]}));
		return v[0];
	}
	int idx = bins(v[1], v[0]);
	vector<int> vv = {v[0][idx]};
	int idx1 = bins(vv, v[1]);
	vector<int> ans;
	for(int i = idx + 1; i < v[0].size(); i++) ans.pb(v[0][i]);
	for(int i = 0; i <= idx; i++) ans.pb(v[0][i]);
	for(int i = idx1; i < v[1].size(); i++) ans.pb(v[1][i]);
	for(int i = 0; i < idx1; i++) ans.pb(v[1][i]);
	return ans;
}

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