Submission #260003

#	Time	Username	Problem	Language	Result	Execution time	Memory
260003		ant101	Shortcut (IOI16_shortcut)	C++14	71 / 100	2062 ms	2048 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
#define INF 1000000
#define inf 1000000000000000
#define F first
#define S second
 
#define ll long long
#define MID ((l+r)/2)
 
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
 
ll pre[10000000];
int n;
int d[1000000];
int C;
bool possble(ll K){
	ll maxsum=inf;
	ll minsum=-inf;
	ll maxdif=inf;
	ll mindif=-inf;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(-pre[i]+pre[j]+d[j]+d[i]>K){
				ll cons = K - C - d[j] - d[i];
				maxsum = min(maxsum, pre[i]+pre[j] + cons);
				minsum = max(minsum, pre[i]+pre[j] - cons);
				maxdif = min(maxdif, pre[j]-pre[i] + cons);
				mindif = max(mindif, pre[j]-pre[i] - cons);
			}
		}
	}
	//cout<<minsum<<" "<<maxsum<<endl;
	if(maxsum<minsum || maxdif<mindif) return false;
	int cursum=n;
	int curdif=0;
	for(int i=0;i<n;i++){
		while(cursum>0 && pre[cursum-1]+pre[i]>=minsum) cursum--;
		while(curdif<n && pre[curdif]-pre[i]<mindif) curdif++;
		int pos = max(cursum,max(curdif,i+1));
		if(pos<n && pre[i]+pre[pos]<=maxsum && pre[pos]-pre[i]<=maxdif) return true;
	}
	return false;
}
 
 
long long find_shortcut(int N, vector<int> L, vector<int> F, int c){
	n = N;
	C = c;
	for(int i=0;i<n;i++) d[i] = F[i];
	for(int i=1;i<n;i++) pre[i] = pre[i-1] + L[i-1];
	ll l=0,r=1000000000000000;
	ll m;
	ll ans=inf;
	while(l<=r){
		//cout<<MID<<endl;
		if(possble(MID)) ans=MID,r = MID-1;
		else l=MID+1;
	}
	//cout<<possble(3)<<endl;
	//assert(possble(r) && possble(r+1));
	return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:55:5: warning: unused variable 'm' [-Wunused-variable]
  ll m;
     ^

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