제출 #1222966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222966		thelegendary08	가장 긴 여행 (IOI23_longesttrip)	C++17	85 / 100	6 ms	432 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)
{
	vi c1; vi c2;
	c1.pb(0); c2.pb(1);
	int ptr = 2;
	while(ptr < N){
		bool a1 = are_connected({c1.back()}, {ptr});
		bool a2 = are_connected({c2.back()}, {ptr});
		if(a1){
			c1.pb(ptr);
		}
		else if(a2){
			c2.pb(ptr);
		}
		else{
			reverse(c2.begin(), c2.end());
			for(auto u : c2){
				c1.pb(u); 
			}
			c2 = {ptr};
		}
		// 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;
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:23:55: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   23 |                 bool a1 = are_connected({c1.back()}, {ptr});
      |                                                       ^~~
longesttrip.cpp:23:55: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:24:55: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   24 |                 bool a2 = are_connected({c2.back()}, {ptr});
      |                                                       ^~~
longesttrip.cpp:24:55: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:36:31: warning: narrowing conversion of 'ptr' from 'long long int' to 'int' [-Wnarrowing]
   36 |                         c2 = {ptr};
      |                               ^~~
longesttrip.cpp:36: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: 45 / 60