Submission #1312909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312909		Jawad_Akbar_JJ	가장 긴 여행 (IOI23_longesttrip)	C++20	85 / 100	6 ms	436 KiB

longesttrip

#include <iostream>
#include <vector>
#include <algorithm>

#include "longesttrip.h"

using namespace std;

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 (v.size() == 0){
			cout<<l<<" "<<r<<" "<<m<<" "<<A.size()<<endl;
			cout<<1 / 0;
		}
		if (are_connected(v, B))
			r = m;
		else
			l = m;
	}
	return r;
}

vector<int> longest_trip(int n, int D){
	vector<int> A = {0}, B, v;

	for (int i=1;i<n;i++){
		if (are_connected({A.back()}, {i})){
			A.push_back(i);
			if (B.size() > 0 and are_connected({i}, {B.back()})){
				reverse(begin(B), end(B));
				A.insert(A.end(), B.begin(), B.end());
				B.clear();
			}
		}
		else
			B.push_back(i);
		if (A.size() < B.size())
			swap(A, B);
	}

	// cout<<"done1"<<endl;
	if (B.size() == 0 or are_connected(A, B) == 0)
		return A;
	// cout<<"here"<<endl;
	int l1 = get(A, B), l2 = get(B, {A[l1]});
	if (l2 == 0)
		swap(A, B), swap(l1, l2);

	// cout<<"///////////////////////\n";
	// for (int i : A)
	// 	cout<<i<<' ';
	// cout<<'\n';
	// for (int i : B)
	// 	cout<<i<<' ';
	// cout<<'\n';
	// cout<<l1<<" "<<l2<<endl;
	// cout<<"///////////////////////\n";

	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;
}

Compilation message (stderr)

longesttrip.cpp: In function 'int get(std::vector<int>, std::vector<int>)':
longesttrip.cpp:17:33: warning: division by zero [-Wdiv-by-zero]
   17 |                         cout<<1 / 0;
      |                               ~~^~~

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