제출 #842737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842737		errorgorn	가장 긴 여행 (IOI23_longesttrip)	C++17	85 / 100	13 ms	1224 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

#define G are_connected

int n;
vector<vector<signed> > v;

vector<signed> rev(vector<signed> v){
	reverse(all(v));
	return v;
}

vector<signed> concat(vector<signed> a,vector<signed> b){
	a.insert(a.end(),all(b));
	return a;
}

vector<signed> longest_trip(signed N, signed D){
    n=N;
    v.clear();
    
    rep(x,0,n) v.pub({x});
    
    while (sz(v)>=3){
		swap(v.back(),v[rng()%sz(v)]); vector<signed> a=v.back(); v.pob();
		swap(v.back(),v[rng()%sz(v)]); vector<signed> b=v.back(); v.pob();
		swap(v.back(),v[rng()%sz(v)]); vector<signed> c=v.back(); v.pob();
		
		if (rng()%2==0) swap(b,a);
		if (rng()%3==0) swap(c,a);
		else if (rng()%2==0) swap(c,b);
		
		if (G({a.back()},{b.back()})){
			swap(a,c);
			v.pub(a);
			v.pub(concat(b,rev(c)));
			continue;
		}
		
		if (G({a.back()},{c.back()})){
			swap(a,b);
		}
		
		vector<signed> d;
		if (!v.empty()){
			swap(v.back(),v[rng()%sz(v)]); d=v.back();
		}
		
		if (!d.empty() && G({a.back()},{d.back()})){
			v.pob();
			v.pub(concat(a,rev(d)));
			v.pub(concat(b,rev(c)));
		}
		else{
			v.pub(a);
			v.pub(concat(b,rev(c)));
		}
	}
	
	//cout<<"2 cyc"<<endl;
	//for (auto it:v[0]) cout<<it<<" "; cout<<endl;
	//for (auto it:v[1]) cout<<it<<" "; cout<<endl;
	
	if ((sz(v[0])==1 || G({v[0].front()},{v[0].back()})) && (sz(v[1])==1 || G({v[1].front()},{v[1].back()}))){
		vector<signed> l=v[0],r=v[1];
		
		if (!G(v[0],v[1])) return (sz(v[0])>sz(v[1])?v[0]:v[1]);
		
		while (sz(l)>1){
			vector<signed> a,b;
			rep(x,0,sz(l)/2) a.pub(l[x]);
			rep(x,sz(l)/2,sz(l)) b.pub(l[x]);
			
			if (G(a,r)) l=a;
			else l=b;
		}
		while (sz(r)>1){
			vector<signed> a,b;
			rep(x,0,sz(r)/2) a.pub(r[x]);
			rep(x,sz(r)/2,sz(r)) b.pub(r[x]);
			
			if (G(l,a)) r=a;
			else r=b;
		}
		
		int idxl,idxr;
		rep(x,0,sz(v[0])) if (v[0][x]==l[0]) idxl=x;
		rep(x,0,sz(v[1])) if (v[1][x]==r[0]) idxr=x;
		
		vector<signed> res;
		rep(x,0,sz(v[0])) res.pub(v[0][(idxl+1+x)%sz(v[0])]);
		rep(x,0,sz(v[1])) res.pub(v[1][(idxr+x)%sz(v[1])]);
		return res;
	}
	else{
		if (G({v[0].front()},{v[1].front()})) return concat(rev(v[0]),v[1]);
		if (G({v[0].front()},{v[1].back()})) return concat(rev(v[0]),rev(v[1]));
		if (G({v[0].back()},{v[1].front()})) return concat(v[0],v[1]);
		if (G({v[0].back()},{v[1].back()})) return concat(v[0],rev(v[1]));
		
		return (sz(v[0])>sz(v[1])?v[0]:v[1]);
	}
}

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

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:44:23: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
   44 |     rep(x,0,n) v.pub({x});
      |                       ^
longesttrip.cpp:44:23: warning: narrowing conversion of 'x' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:114:39: warning: 'idxr' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |   rep(x,0,sz(v[1])) res.pub(v[1][(idxr+x)%sz(v[1])]);
      |                                  ~~~~~^~~
longesttrip.cpp:113:39: warning: 'idxl' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |   rep(x,0,sz(v[0])) res.pub(v[0][(idxl+1+x)%sz(v[0])]);
      |                                   ~~~~^~

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