Submission #956423

#	Time	Username	Problem	Language	Result	Execution time	Memory
956423		peteza	Gap (APIO16_gap)	C++14	100 / 100	37 ms	4000 KiB

gap

#include "gap.h"
#include <iostream>
#include <vector>
#include <utility>
using ll = long long;
const ll inf = 2e18;
 
long long findGap(int T, int N) {
	if(T==1) {
		ll cmin=0, cmax=inf, l=0, r=0;
		std::vector<ll> v1, v2;
		while(cmin <= cmax && v1.size() + v2.size() < N) {
			MinMax(cmin, cmax, &l, &r);
			if(l == -1) break;
			v1.push_back(l); if(l != r) v2.push_back(r);
			cmin = l+1; cmax = r-1;
		}
		ll amax = v2.back() - v1.back();
		for(int i=0;i<v1.size()-1;i++) amax = std::max(amax, v1[i+1] - v1[i]);
		for(int i=0;i<v2.size()-1;i++) amax = std::max(amax, v2[i] - v2[i+1]);
		return amax;
	} else {
		ll rmin, rmax, l, r;
		MinMax(0, inf, &rmin, &rmax);
		ll amax = (rmax-rmin)/(N-1), i=1;
      i=amax;
		while(rmin < rmax) {
			for(;i<=inf;i<<=1) {
				MinMax(rmin+1, rmin+i, &l, &r);
				if(l != -1) break;
			}
			//if(i >= amax) i >>= 1;
        //  i = std::max(i, 1ll);
			amax = std::max(amax, l-rmin);
			i=amax;
          rmin = r;
		} 
		return amax;
	}
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:12:47: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |   while(cmin <= cmax && v1.size() + v2.size() < N) {
      |                         ~~~~~~~~~~~~~~~~~~~~~~^~~
gap.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(int i=0;i<v1.size()-1;i++) amax = std::max(amax, v1[i+1] - v1[i]);
      |               ~^~~~~~~~~~~~
gap.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for(int i=0;i<v2.size()-1;i++) amax = std::max(amax, v2[i] - v2[i+1]);
      |               ~^~~~~~~~~~~~

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