Submission #23386

#	Time	Username	Problem	Language	Result	Execution time	Memory
23386		rubabredwan	Gap (APIO16_gap)	C++14	47.41 / 100	93 ms	7796 KiB

gap

/* Bismillahir Rahmanir Rahim */

#include "gap.h"
#include <bits/stdc++.h>

using namespace std;

const long long M = 1e18;

long long mdiff = 0;

void solve(long long st, long long en, long long cnt){
	if(st > en) return;
	long long rng = (en - st + 1LL) / cnt;
	vector<long long>mn, mx;
	for(long long i=st;i<=en;i+=rng){
		long long A, B;
		MinMax(i, min(i + rng - 1LL, en), &A, &B);
		if(A == -1) continue;
		mn.push_back(A);
		mx.push_back(B);
		cnt -= 1 + (A != B);
	}
	for(int i=1;i<mn.size();i++) mdiff = max(mdiff, mn[i] - mx[i-1]);
	for(int i=0;i<mn.size();i++){
		if(mx[i] - mn[i] > mdiff) solve(mn[i], mx[i], cnt+2);
	}
}


long long findGap(int T, int N){
	solve(0, M, N);
	return mdiff;
}

Compilation message (stderr)

gap.cpp: In function 'void solve(long long int, long long int, long long int)':
gap.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<mn.size();i++) mdiff = max(mdiff, mn[i] - mx[i-1]);
               ^
gap.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<mn.size();i++){
               ^

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