Submission #74315

#	Time	Username	Problem	Language	Result	Execution time	Memory
74315		WA_TLE	Shortcut (IOI16_shortcut)	C++14	0 / 100	2 ms	620 KiB

shortcut

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
llint find_shortcut(int in,vector<int>l,vector<int>d,int c){
	//まず、要らない人を除く
	vector<llint>wa;//場所
	vector<llint>di;
	llint i,j;
	vector<llint>eki(in+2);
	wa.pub(-mod);
	di.pub(0);
	llint gebas=0;
	eki[0]=-mod;
	eki[in+1]=mod;
	for(i=0;i<in;i++){
		if(i>0){gebas+=l[i-1];eki[i+1]=gebas;}
		while(gebas-wa.back()<=d[i]-di.back()){wa.pob();di.pob();}
		if(gebas-wa.back()>di.back()-d[i]){wa.pub(gebas);di.pub(d[i]);}
	}
	wa.pub(big);
	di.pub(0);
	llint n=wa.size()-2;
	//とりあえずこれでいらないのは消えた
	//二分探索!
	//n=1だとなんか特別なことになる
	//片方をそこに固定して、それをのぞいて適当にする
	if(n==1){
		//dの最大を探す,そこ出発以外考えなくてよい
		//そこのdをぜろにしてもう一度同じこと
		//つける相手の駅を全探索
		//左と右のでかい側につける
		llint saD=1;
		for(i=0;i<in;i++){if(d[saD]<d[i]){saD=i;}}
		llint mto=d[saD];d[saD]=0;
		wa.clear();di.clear();
		wa.pub(-mod);di.pub(0);gebas=0;
		for(i=0;i<in;i++){
			if(i>0){gebas+=l[i-1];}
			while(gebas-wa.back()<=d[i]-di.back()){wa.pob();di.pob();}
			if(gebas-wa.back()>di.back()-d[i]){wa.pub(gebas);di.pub(d[i]);}
		}
		wa.pub(big);
		di.pub(0);
		llint n=wa.size()-2;
		llint bmin=0,bmax=big;
		vector<llint>iwa;
		vector<llint>idi;
		vector<llint>ieki;
		//左側に一番大きい頂点があるようにうまく変換する
		//iwa[0]=0;
		//idi[0]=0;
		//それ以降はあれ
		saD++;
		//cerr<<"saD"<<saD<<endl;
		if(eki[saD]-wa[1]+di[1]>wa[n]-eki[saD]+di[n]){
			//左がでかいから小さくしたい、かえる
			bmin=wa[n]-eki[saD]+di[n]-1;
			iwa.pub(0);
			idi.pub(0);
			ieki.pub(0);
			int sta=LBI(wa,eki[saD])-1;
			wa[sta+1]=eki[saD];
			for(i=sta;i>=0;i--){
				iwa.pub(iwa.back()+wa[i+1]-wa[i]);
				idi.pub(di[i]);
			}
			for(i=saD-1;i>=0;i--){
				ieki.pub(ieki.back()+eki[i+1]-eki[i]);
			}
		}else{
			//右がでかいから小さくしたい
			//i<=n+1;
			bmin=eki[saD]-wa[1]+di[1]-1;
			iwa.pub(0);
			idi.pub(0);
			ieki.pub(0);
			int sta=UBI(wa,eki[saD]);
			wa[sta-1]=eki[saD];
			for(i=sta;i<di.size();i++){
				iwa.pub(iwa.back()+wa[i]-wa[i-1]);
				idi.pub(di[i]);
			}
			for(i=saD+1;i<eki.size();i++){
				ieki.pub(ieki.back()+eki[i]-eki[i-1]);
			}
		}
		wa=iwa;eki=ieki;di=idi;
		//for(auto it:wa){cout<<it<<" ";}cout<<endl;
		//for(auto it:di){cout<<it<<" ";}cout<<endl;
		
		n=wa.size()-2;
		//すべての0は遠すぎる駅
		//すべてのn+1は番兵
		//すべての1~nは考えるべき駅
		//bmin+1が答えの下限
		bmax=wa[n]-wa[0]+di[n];//自明
		
		
		while(bmax>bmin+1){
			
			llint bgen=(bmax+bmin)/2;
			int stdex=1;
			for(i=n;i>0;i--){
				if(wa[i]-wa[0]+di[i]>bgen){stdex=i;}
				else{break;}
			}
			int stchu=LBI(eki,(1+wa[n]+wa[stdex]+di[n]-di[stdex])/2);
			llint stdis=min(eki[stchu]-wa[stdex]+di[stdex],wa[n]-eki[stchu-1]+di[stdex]);
			if(stdis+c<=bgen){bmax=bgen;}else{bmin=bgen;}
		}
		return mto+bmax;
	}
	llint bmin=0,bmax=wa[n]-wa[1]+di[n]+di[1];
	//for(i=0;i<=n;i++){cerr<<wa[i]<<" "<<di[i]<<endl;}
	while(bmax>bmin+1){
		llint bgen=(bmax+bmin)/2;
		if(di[1]+di[n]+c>bgen){bmin=bgen;continue;}//定数倍
		int uedex=1,stdex=n;//uedex右端->どこまでひだり
		for(i=1;i<=n;i++){
			if(wa[n]-wa[i]+di[n]+di[i]>bgen){uedex=i;}
			else{break;}
		}
		//ここを二分探索にする
		for(i=n;i>0;i--){
			if(wa[i]-wa[1]+di[1]+di[i]>bgen){stdex=i;}
			else{break;}
		}
		if(stdex==1){stdex=2;}
		if(uedex==n){uedex=n-1;}
		//uedex,stdexがわかった
		if(uedex>=stdex){bmin=bgen;continue;}
		//あ
		//0 - uedex,stdex - n-1
		int uechu=LBI(eki,(1+wa[uedex]+wa[1]+di[uedex]-di[1])/2);
		llint uedis=min(eki[uechu]-wa[1]+di[1],wa[uedex]-eki[uechu-1]+di[uedex]);
		
		int stchu=LBI(eki,(1+wa[n]+wa[stdex]+di[n]-di[stdex])/2);
		llint stdis=min(eki[stchu]-wa[stdex]+di[stdex],wa[n]-eki[stchu-1]+di[stdex]);
		
		if(uedis+stdis+c<=bgen){bmax=bgen;}else{bmin=bgen;}
	}
	return bmax;
}

Compilation message (stderr)

shortcut.cpp: In function 'llint find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=sta;i<di.size();i++){
              ~^~~~~~~~~~
shortcut.cpp:132:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=saD+1;i<eki.size();i++){
                ~^~~~~~~~~~~
shortcut.cpp:57:10: warning: unused variable 'j' [-Wunused-variable]
  llint i,j;
          ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3