Submission #956215

#	Time	Username	Problem	Language	Result	Execution time	Memory
956215		peteza	Gap (APIO16_gap)	C++14	42.65 / 100	55 ms	3928 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 = 1, i=1;
		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);
			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: 12.6460549623 / 70