Submission #841857

#	Time	Username	Problem	Language	Result	Execution time	Memory
841857		anhduc2701	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	15 ms	856 KiB

longesttrip

#include<bits/stdc++.h>
#include "longesttrip.h"
#define pb push_back
#define fi first
#define se second 
using namespace std;
typedef long long ll;
int n;
pair<int,int> getpos(vector<int>A,vector<int>B){
	if(A.size()==1 && B.size()==1){
		return {A[0],B[0]};
	}
	else{
		int mid1=((int)(A.size())-1)/2;
		vector<int>X;
		for(int i=0;i<=mid1;i++){
			X.pb(A[i]);
		}
		if(A.size() > 1 && !are_connected(X,B)){
			X.clear();
			for(int i=mid1+1;i<(int)A.size();i++){
				X.pb(A[i]);
			}
		}
		int mid2=((int)(B.size())-1)/2;
		vector<int>Y;
		for(int i=0;i<=mid2;i++){
			Y.pb(B[i]);
		}
		if(B.size() ==1 || (are_connected(X,Y))){
			return getpos(X,Y);
		}
		else{
			Y.clear();
			for(int i=mid2+1;i<(int)B.size();i++){
				Y.pb(B[i]);
			}
			return getpos(X,Y);
		}
	}
}
vector<int> longest_trip(int N,int D){
	n=N;
	if(D==3){
		vector<int>K;
		for(int i=0;i<N;i++){
			K.pb(i);
		}
		return K;
	}
	else if(D==2){
		vector<int>K;
		if(are_connected(vector<int>(1,0),vector<int>(1,1))){
			K.pb(0);
			K.pb(1);
		}
		else{
			K.pb(0);
			K.pb(2);
			K.pb(1);
		}
		while((int)(K.size())<N){
			int i=(int)(K.size());
			if(are_connected(vector<int>(1,K[0]),vector<int>(1,i))){
				K.insert(K.begin(),i);
			}
			else{
				K.pb(i);
			}
		}
		return K;
	}
	else{
		vector<int>Line1;
		vector<int>Line2;
		Line1.pb(0);
		Line2.pb(1);
		int j=2;
		while(j<N){
			if(j+2<=N){
				if(are_connected(vector<int>(1,Line2.back()),vector<int>(1,j))){
					Line2.pb(j);
					j++;
				}
				else{
					bool d=are_connected(vector<int>(1,j),vector<int>(1,j+1));
					if(d==0){
						Line2.pb(j+1);
						bool d1=are_connected(vector<int>(1,j),vector<int>(1,Line1.back()));
						if(d1==1){
							Line1.pb(j);
						}
						else{
							reverse(Line1.begin(),Line1.end());
							for(auto v:Line1){
								Line2.pb(v);
							}
							Line1.clear();
							Line1.pb(j);
						}
						j+=2;
					}
					else{
						if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,j))){
							Line1.pb(j);
							Line1.pb(j+1);
							j+=2;
						}
						else{
							reverse(Line1.begin(),Line1.end());
							for(auto v:Line1){
								Line2.pb(v);
							}
							Line1.clear();
							Line1.pb(j);
							Line1.pb(j+1);
							j+=2;
						}
					}
				}
			}
			else{
				if(are_connected(vector<int>(1,Line2.back()),vector<int>(1,j))){
					Line2.pb(j);
					j++;
				}
				else if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,j))){
					Line1.pb(j);
					j++;
				}
				else{
					reverse(Line1.begin(),Line1.end());
					for(auto v:Line1){
						Line2.pb(v);
					}
					Line1.clear();
					Line1.pb(j);
					j++;
				}
			}
		}
		if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,Line2.back()))){
			reverse(Line1.begin(),Line1.end());
			for(auto v:Line1){
				Line2.pb(v);
			}
			Line1.clear();
			return Line2;
		}
		else if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,Line2[0]))){
			for(auto v:Line2){
				Line1.pb(v);
			}
			Line2.clear();
			return Line1;
		}
		else if(are_connected(vector<int>(1,Line1[0]),vector<int>(1,Line2.back()))){
			for(auto v:Line1){
				Line2.pb(v);
			}
			Line1.clear();
			return Line2;
		}
		else if(are_connected(vector<int>(1,Line1[0]),vector<int>(1,Line2[0]))){
			reverse(Line2.begin(),Line2.end());
			for(auto v:Line1){
				Line2.pb(v);
			}
			Line1.clear();
			return Line2;
		}
		else{
			if(are_connected(Line1,Line2)){
				pair<int,int>g=getpos(Line1,Line2);
				vector<int>ans;
				for(int i=0;i<(int)(Line1.size());i++){
					if(Line1[i]==g.fi){
						for(int j=i+1;j<(int)(Line1.size());j++){
							ans.pb(Line1[j]);
						}
						for(int j=0;j<=i;j++){
							ans.pb(Line1[j]);
						}
					}
				}
				for(int i=0;i<(int)Line2.size();i++){
					if(Line2[i]==g.se){
						for(int j=i;j<(int)(Line2.size());j++){
							ans.pb(Line2[j]);
						}
						for(int j=0;j<i;j++){
							ans.pb(Line2[j]);
						}
					}
				}
				return ans;
			}
			else{
				if(Line1.size()>Line2.size()){
					return Line1;
				}
				else{
					return Line2;
				}
			}
		}
	}
}

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