Submission #246009

#	Time	Username	Problem	Language	Result	Execution time	Memory
246009		wwdd	Gap (APIO16_gap)	C++14	100 / 100	76 ms	3364 KiB

gap

#include <stdio.h>
#include <stdlib.h>
#include "gap.h"

#include <vector>
using ll = long long;
using vl = std::vector<ll>;
using namespace std;
ll lol(ll n) {
	vl wa,wb;
	ll lo = 0,hi = 1e18;
	ll ok = (n+1)/2;
	for(int i=0;i<ok;i++) {
		ll ma,mi;
		MinMax(lo,hi,&mi,&ma);
		lo = mi+1;hi = ma-1;
		wa.push_back(mi);
		wb.push_back(ma);
	}
	if(n&1) {wa.pop_back();}
	for(int i=wb.size()-1;i>=0;i--) {wa.push_back(wb[i]);}
	ll res = 0;
	for(int i=1;i<n;i++) {
		res = max(res,wa[i]-wa[i-1]);
	}
	return res;
}
ll solve(ll n) {
	ll lo = 0,hi = 1e18;
	ll st,ed;
	MinMax(lo,hi,&st,&ed);
	ll bd = (ed-st+n-2)/(n-1);
	vl w;
	w.push_back(st);
	lo = st+1;
	for(int i=0;i<n-1;i++) {
		if(lo > ed) {break;}
		hi = min(lo+bd,ed);
		ll sa,sb;
		MinMax(lo,hi,&sa,&sb);
		if(sa != -1) {
			w.push_back(sa);
			w.push_back(sb);
		}
		lo = hi+1;
	}
	w.push_back(ed);
	ll res = 0;
	for(int i=1;i<w.size();i++) {
		res = max(res,w[i]-w[i-1]);
	}
	return res;
}
long long findGap(int T, int N) {
	if(T == 1) {
		return lol(N);
	} else {
		return solve(N);
	}
}

Compilation message (stderr)

gap.cpp: In function 'll solve(ll)':
gap.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<w.size();i++) {
              ~^~~~~~~~~

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