Submission #131786

#	Time	Username	Problem	Language	Result	Execution time	Memory
131786		junodeveloper	Gap (APIO16_gap)	C++14	100 / 100	82 ms	2416 KiB

gap

#include "gap.h"
#include <vector>
#include <algorithm>
using namespace std;
 
long long findGap(int T, int N) {
	long long s, e, mn, mx, res = 0;
	if(T == 1) {
		s=0, e=1e18;
		vector<long long> v;
		while(s <= e && N > 0) {
			MinMax(s, e, &mn, &mx);
			if(mn == -1) break;
			v.push_back(mn), N--;
			if(mn != mx) v.push_back(mx), N--;
			s = mn + 1, e = mx - 1;
		}
		sort(v.begin(), v.end());
		for(int i=0; i+1<v.size(); i++)
			res = max(res, v[i+1] - v[i]);
	} else {
		s=0, e=1e18;
		MinMax(s, e, &mn, &mx);
		long long len = (mx - mn + N - 2) / (N - 1);
		vector<long long> v;
		s=mn, e=mx;
		while(s <= e) {
			MinMax(s, s + len, &mn, &mx);
			if(mn != -1) {
				v.push_back(mn);
				if(mn != mx) v.push_back(mx);
			}
			s += len + 1;
		}
		sort(v.begin(), v.end());
		res = len;
		for(int i=0; i+1<v.size(); i++)
			res = max(res, v[i+1] - v[i]);
	}
	return res;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i+1<v.size(); i++)
                ~~~^~~~~~~~~
gap.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i+1<v.size(); i++)
                ~~~^~~~~~~~~

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