제출 #1234400

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

longesttrip

#include "longesttrip.h"
#include <queue>
#include <iostream>
//#include <assert.h>

using namespace std;

#define pb push_back
#define dcerr if(1==0)cerr

vector<int> longest_trip(int n, int d){
	vector<int> ans;
	if(d==2){
		// surely there still exists a round trip...
		// why is this screaming linked list :(
		vector<int> starts;
		if(!are_connected({0}, {n-1})){
			starts.pb(0);
		}
		for(int i=1; i<n; i++){
			if(!are_connected({i-1}, {i})){
				starts.pb(i);
			}
		}
		if(starts.size()==0){
			d=3; // go do the easy case (0,1,2,...)
		} else{
			// we certainly have breaks somewhere.
			starts.pb(starts[0]+n);
			bool forwards=false;
			for(int j=0; j<starts.size()-1; j++){				
				forwards = !forwards;
				if(forwards){
					// forwards
					for(int i=starts[j]; i<starts[j+1]; i++){
						ans.pb(i%n);
					}
				} else{
					// backwards
					for(int i=starts[j+1]-1; i>starts[j]-1; i--){
						ans.pb(i%n);
					}
				}
			}
		}

	}
	if(d==3){
		for(int i=0; i<n; i++){
			ans.pb(i);
		}
	}

	if(d==1){
		// the boss fight
		vector<int> link(n, -1);
		int start1, start2, end1, end2;
		int a,b,c;
		queue<int> q;
		a=are_connected({0}, {1});
		b=are_connected({1}, {2});
		c=are_connected({0}, {2});

		if(a){
			start1=0;
			link[0]=1;
			end1=1;
		} else if(b){
			start1=1;
			link[1]=2;
			end1=2;
		} else if(c){
			start1=0;
			link[0]=2;
			end1=2;
		}
		for(int i=0; i<n; i++){
			if(i!=start1 && i!=end1){
				q.push(i);
			}
		}
		a=-1;b=-1;c=-1;
		start2=-1;end2=-1;


		while(!q.empty()){
			// a
			a=end1;
			// b
			if(start2==-1){
				b=q.front();
				q.pop();
				start2=b;
				end2=b;
			}
			// c
			if(c==-1 && !q.empty()){
				c=q.front();
				q.pop();
			}

			// at this point: b and c are both real values. 

			//assert(a!=b);
			//assert(b!=c);
			//assert(a!=c);
			
			if(are_connected({a}, {b})){
				// a-b (join the lists)
				link[a]=b;
				end1=end2;
				a=end2;
				start2=-1;
				end2=-1;
				b=-1;
			} else if(c!=-1 && are_connected({a}, {c})){
				// a-c (go to list1)
				end1=c;
				link[a]=c;
				c=-1;
			} else if(c!=-1){ //|| are_connected({b}, {c})){
				// b-c (go to list2)
				start2=c;
				link[c]=b;
				b=c;
				c=-1;
			}
		}
		// recall that:
		// a = the end of the first string
		// b = the start of the second string (possibly -1)
		// c = the new value to add (possibly -1)
		
		// if c has a value, then we aren't really done...
		if(c != -1){
			// we aren't done
			// c being something means that b is nothing (!)
			if(are_connected({a}, {c})){
				link[a]=c;
				end1=c;
				a=c;
				c=-1;
			} else{
				start2=c;
				end2=c;
			} // now to append c...
		}
		
		// <--- DEBUGGING --->
		dcerr<<"start1, end1: "<<start1<<", "<<end1<<"\n";
		dcerr<<"start2, end2: "<<start2<<", "<<end2<<"\n";

		int cur=start1;
		vector<int> ans1={start1};
		while(link[cur] != -1){
			cur = link[cur];
			ans1.pb(cur);
		}
		
		if(start2==-1){
			return ans1;
		} // else...
		  // in this case we have to do some freaky shit

		cur=start2;
		vector<int> ans2={start2};
		while(link[cur] != -1){
			cur = link[cur];
			ans2.pb(cur);
		}

		// ans1+ans2=everything (I hope)
		if(!are_connected(ans1, ans2)){
			if(ans1.size() >= ans2.size()){
				return ans1;
			} else{
				return ans2;
			}
		}
		dcerr<<"$ they are connected...\n";
		// oh shit they're connected...
		vector<int> finalanswer;
		vector<int> secondary_endpoints = {start2};
		if(start2 != end2) secondary_endpoints.pb(end2);
		if(are_connected({start1, end1}, secondary_endpoints)){
			// simple case.
			if(are_connected({end1}, {start2})){
				dcerr<<"$ simple case 1.\n";
				for(int i=0; i<ans1.size(); i++) finalanswer.pb(ans1[i]);
				for(int i=0; i<ans2.size(); i++) finalanswer.pb(ans2[i]);
			} else if(are_connected({end1}, {end2})){
				for(int i=0; i<ans1.size(); i++) finalanswer.pb(ans1[i]);
				for(int i=ans2.size()-1; i>-1; i--) finalanswer.pb(ans2[i]);
			} else if(are_connected({start1}, {start2})){
				for(int i=ans1.size()-1; i>-1; i--) finalanswer.pb(ans1[i]);
				for(int i=0; i<ans2.size(); i++) finalanswer.pb(ans2[i]);
			} else{ //start1, end2
				for(int i=ans1.size()-1; i>-1; i--) finalanswer.pb(ans1[i]);
				for(int i=ans2.size()-1; i>-1; i--) finalanswer.pb(ans2[i]);
			}
			return finalanswer;
		}
		
		dcerr<<"$ not as simple.\n";
		// not-simple case. FUUUUUCCKKK

		// both lists are cyclic... binary search? idk
		int s1=ans1.size(),s2=ans2.size();
		// find the link in ans1...
		int a1_connector;
		// ...using b*nary search (ew)
		int l=0, r=s1-1, m=(r+l)/2;
		vector<int> curvec(2,0);
		for(int i=l; i<=m; i++) curvec.pb(ans1[i]);
		while(curvec.size()>1){
			if(are_connected({curvec}, {ans2})){
				r = m;
			} else{
				l = m+1;
			}
			m = (l+r)/2;
			curvec.clear();
			for(int i=l; i<=m; i++) curvec.pb(ans1[i]);
		}
		// now we have curvec.size()==1
		a1_connector = l;
		int a1_nc = curvec[0];
		curvec.clear();

		// time to find a2_connector. 
		int a2_connector;
		l=0; r=s2-1; m=(r+l)/2;
		for(int i=l; i<=m; i++) curvec.pb(ans2[i]);
		while(curvec.size()>1){
			if(are_connected({curvec}, {a1_nc})){
				r = m;
			} else{
				l = m+1;
			}
			m = (l+r)/2;
			curvec.clear();
			for(int i=l; i<=m; i++) curvec.pb(ans2[i]);
		}
		a2_connector = l;
		// now we should have everything we need :)
		for(int i=a1_connector+1; i<a1_connector+s1+1; i++){
			finalanswer.pb(ans1[i%s1]);
		} for(int i=a2_connector; i<a2_connector+s2; i++){
			finalanswer.pb(ans2[i%s2]);
		}
		return finalanswer;
	}
	return ans;
}

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