Submission #344172

#	Time	Username	Problem	Language	Result	Execution time	Memory
344172		juggernaut	Gap (APIO16_gap)	C++14	100 / 100	68 ms	3272 KiB

gap

#include<bits/stdc++.h>
#include"gap.h"
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
typedef long long ll;
ll ans,mn,mx,n,l=-1,r=1e19+1;
vector<ll>x,y;
ll findGap(int t, int N){
	n=N;
	if(t==1){
		while(x.size()+y.size()<n){
			l++,r--;
			MinMax(l,r,&l,&r);
			x.push_back(l);
			y.push_back(r);
		}
	}else{
		MinMax(l,r,&l,&r);
		x.push_back(l),y.push_back(r);
		ll s=r-l+1LL;
		s/=n;
		s++;
		for(ll i=l;i+1<r;i+=s){
			ll nx=min(r-1,i+s);
			MinMax(i+1,nx,&mn,&mx);
			if(mn!=-1)x.push_back(mn);
			if(mx!=-1)x.push_back(mx);
		}
    }
  for(int i=y.size()-1;i>=0;i--)x.push_back(y[i]);
	for(int i=0;i+1<x.size();i++)ans=max(ans,x[i+1]-x[i]);
	return ans;
}

Compilation message (stderr)

gap.cpp:9:27: warning: overflow in conversion from 'double' to 'll' {aka 'long long int'} changes value from '1.0e+19' to '9223372036854775807' [-Woverflow]
    9 | ll ans,mn,mx,n,l=-1,r=1e19+1;
      |                       ~~~~^~
gap.cpp: In function 'll findGap(int, int)':
gap.cpp:14:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   14 |   while(x.size()+y.size()<n){
      |         ~~~~~~~~~~~~~~~~~^~
gap.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i+1<x.size();i++)ans=max(ans,x[i+1]-x[i]);
      |              ~~~^~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70