Submission #868022

#	Time	Username	Problem	Language	Result	Execution time	Memory
868022		Lib	Shortcut (IOI16_shortcut)	C++14	0 / 100	1 ms	6488 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;
long long lim=1000000000000000000;
long long BoundTopLeft,BoundTopRight,BoundBottomLeft,BoundBottomRight; //Where the lines that forms the current bound cuts the X-axis
long long TopLeft,TopRight,BottomLeft,BottomRight; //Where the lines that forms the current square cuts the Y-axis
int n;
long long Mainline[1000003];
long long Secondline[1000003];
long long PrefixMax[1000003];
long long PrefixMaxpos[1000003];
long long Extraline;
long long C,X,Y;
long long cntok;
long long MaxDiffpos[1000003];
long long MinSumpos[1000003];
long long Curmin,Curmax;

long long PossibleDiameter(long long Dist){
	//Dist=8;
	BoundTopLeft=-lim;
	BoundTopRight=lim;
	BoundBottomLeft=-lim;
	BoundBottomRight=lim;
	cntok=0;
	int k;
		for(int i=2;i<=n;i++){
		//Creating the square with rightmost left bound obtainable from station i
		k=MaxDiffpos[i];
		C=Dist-(Extraline+Secondline[i]+Secondline[k]);
		X=Mainline[i];
		Y=Mainline[k];
		TopLeft=X-C-Y;
		TopRight=X+C+Y;
		BottomLeft=X-C+Y; 
		BottomRight=X+C-Y; 
		if((Secondline[i]+Secondline[k]+Mainline[i]-Mainline[k])>Dist){
		BoundTopLeft=max(BoundTopLeft,TopLeft);
		BoundTopRight=min(BoundTopRight,TopRight);
		BoundBottomRight=min(BoundBottomRight,BottomRight);
		BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
		}
		//And the square with the leftmost right bound
		k=MinSumpos[i];
		C=Dist-(Extraline+Secondline[i]+Secondline[k]);
		X=Mainline[i];
		Y=Mainline[k];
		TopLeft=X-C-Y;
		TopRight=X+C+Y;
		BottomLeft=X-C+Y; 
		BottomRight=X+C-Y; 
		if((Secondline[i]+Secondline[k]+Mainline[i]-Mainline[k])>Dist){
		BoundTopLeft=max(BoundTopLeft,TopLeft);
		BoundTopRight=min(BoundTopRight,TopRight);
		BoundBottomRight=min(BoundBottomRight,BottomRight);
		BoundBottomLeft=max(BoundBottomLeft,BottomLeft);
		}
		}
	if(BoundTopLeft>BoundBottomRight||BoundBottomLeft>BoundTopRight){
		return 0;
	}
	for(int k=1;k<n;k++){
			for(int l=k+1;l<=n;l++){
				if((BoundTopLeft <= Mainline[l]-Mainline[k])&&(Mainline[l]-Mainline[k] <= BoundBottomRight)&&(BoundBottomLeft <= Mainline[k]+Mainline[l])&&(Mainline[k]+Mainline[l] <= BoundTopRight)){
						return 1;
					}
				if((Secondline[l]+Secondline[k]+Mainline[l]-Mainline[k])>Dist){
				}else{
					cntok++;
				}	
			}
		}
		if(cntok==n*(n-1)/2){
			return 1;
		}
		return 0;
}

long long find_shortcut(int N, vector <int> L, vector<int> D, int c){
	long long temp=0;
	n=N;
	for(int i=2;i<=n;i++){
		temp=L[i-2];
		Mainline[i]=Mainline[i-1]+temp;
	}
	for(int i=1;i<=n;i++){
		Secondline[i]=D[i-1];
	}
	Extraline=c;
	Curmin=lim;
	Curmax=-lim;
	for(int i=1;i<n;i++){
		if(Mainline[i]-Secondline[i]>Curmax){
			Curmax=Mainline[i]-Secondline[i];
			MaxDiffpos[i+1]=i;
		}else{
			MaxDiffpos[i+1]=MaxDiffpos[i];
		}
		if(Mainline[i]+Secondline[i]<Curmin){
			Curmin=Mainline[i]+Secondline[i];
			MinSumpos[i+1]=i;
		}else{
			MinSumpos[i+1]=MinSumpos[i];
		}
	}
	long long l=1,r=lim;
	long long mid;
	while(r-l>=1){
		mid=(r+l)/2;
		if(PossibleDiameter(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	if(PossibleDiameter(l)){
		return l;
	}else if(PossibleDiameter(r)){
		return r;
	}
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^

• 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