Submission #1222994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222994		thelegendary08	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	8 ms	436 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0;i<n;i++)
#define FOR(i, k, n) for(int i = k;i<n;i++)
#define pb push_back
#define vi vector<signed>
#define pii pair<int,int>
#define mp make_pair
#define vpii vector<pii>
#define vvi vector<vi>
#define vb vector<bool>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
const int mxn = 260;
vvi adj(mxn);
std::vector<signed> longest_trip(signed N, signed D)
{
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vi c1; vi c2;
	c1.pb(0); c2.pb(1);
	int ptr = 2;
	int hehe = -1;
	while(ptr < N){
		bool rnd = rng();
		bool a1, a2;
		if(rnd){
			a1 = are_connected({c1.back()}, {ptr});
			if(hehe == 0)a2 = !a1;
			else a2 = are_connected({c2.back()}, {ptr});
		}
		else{
			a2 = are_connected({c2.back()}, {ptr});
			if(hehe == 0)a1 = !a2;
			else a1 = are_connected({c1.back()}, {ptr});
		}
		if(a1 && a2){
			c1.pb(ptr);
			reverse(c2.begin(), c2.end());
			for(auto u : c2){
				c1.pb(u); 
			}
			ptr++;
			if(ptr == N){
				c2 = {c1.back()}; c1.pop_back();
			}
			else c2 = {ptr};
			hehe = -1;
		}
		else if(a1){
			c1.pb(ptr); if(hehe == -1)hehe = 0; else hehe = -1;
		}
		else if(a2){
			c2.pb(ptr); if(hehe == -1)hehe = 0; else hehe = -1;
		}
		else{
			reverse(c2.begin(), c2.end());
			for(auto u : c2){
				c1.pb(u); 
			}
			c2 = {ptr};
			hehe = -1;
		}
		// vout(c1); vout(c2);
		ptr++;
	}
	
	bool g = are_connected(c1, c2);
	if(!g){
		if(c1.size() < c2.size())swap(c1, c2);
		return c1;
	}
	vi ah; ah.pb(c2[0]); if(c2.size() > 1)ah.pb(c2.back());
	bool a1 = are_connected({c1[0]}, ah);
	if(a1){
		bool b1 = are_connected({c1[0]}, {c2[0]});
		if(b1){
			reverse(c1.begin(), c1.end());
			for(auto u : c2)c1.pb(u); return c1;
		}
		else{
			for(auto u : c1)c2.pb(u); return c2;
		}
	}

	bool a2 = are_connected({c1.back()}, ah);
	if(a2){
		bool b2 = are_connected({c1.back()}, {c2[0]});
		if(b2){
			for(auto u : c2)c1.pb(u); return c1;
		}
		else{
			reverse(c2.begin(), c2.end());
			for(auto u : c2)c1.pb(u); return c1;
		}
	}
	
	int lo = 0; int hi = c1.size() - 1;
	while(lo < hi){
		int mid = lo + (hi - lo) / 2;
		vi tmp;
		f0r(i, mid + 1){
			tmp.pb(c1[i]);
		}
		bool h = are_connected(tmp, c2);
		if(h){
			hi = mid;
		}
		else{
			lo = mid + 1;
		}
	}
	int c1l = lo;
	lo = 0; hi = c2.size() - 1;
	while(lo < hi){
		int mid = lo + (hi - lo) / 2;
		vi tmp; 
		f0r(i, mid + 1){
			tmp.pb(c2[i]);
		}
		bool h = are_connected({c1[c1l]}, tmp);
		if(h){
			hi = mid;
		}
		else{
			lo = mid + 1;
		}
	}
	int c2l = lo;
	vi ans;
	FOR(i, c1l + 1, c1.size()){
		ans.pb(c1[i]);
	}
	f0r(i, c1l+1){
		ans.pb(c1[i]);
	}
	FOR(i, c2l, c2.size()){
		ans.pb(c2[i]);
	}
	f0r(i, c2l){
		ans.pb(c2[i]);
	}
	return ans;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:28:58: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   28 |                         a1 = are_connected({c1.back()}, {ptr});
      |                                                          ^~~
longesttrip.cpp:28:58: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:30:63: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   30 |                         else a2 = are_connected({c2.back()}, {ptr});
      |                                                               ^~~
longesttrip.cpp:30:63: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:33:58: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   33 |                         a2 = are_connected({c2.back()}, {ptr});
      |                                                          ^~~
longesttrip.cpp:33:58: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:35:63: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   35 |                         else a1 = are_connected({c1.back()}, {ptr});
      |                                                               ^~~
longesttrip.cpp:35:63: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:47:36: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   47 |                         else c2 = {ptr};
      |                                    ^~~
longesttrip.cpp:47:36: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:61:31: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   61 |                         c2 = {ptr};
      |                               ^~~
longesttrip.cpp:61:31: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]

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