제출 #394409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
394409		jsannemo	Gap (APIO16_gap)	C++14	70 / 100	71 ms	2252 KiB

gap

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

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<ll> qs;

pair<ll, ll> query(ll lo, ll hi) {
	pair<ll, ll> res;
	MinMax(lo, hi, &res.first, &res.second);
	/// cerr << "q " << lo << " " << hi << endl;
	if (res.first != -1) {
		qs.push_back(res.first);
		if (res.first != res.second) qs.push_back(res.second);
	}
	return res;
}

long long findGap(int T, int N) {
	ll lo = 0;
	ll hi = 1'000'000'000'000'000'000;
	tie(lo, hi) = query(lo, hi);
	++lo;
	--hi;
	for (int k = N - 1; k >= 1; --k) {
		ll nask = lo + (hi - lo) / k;
		query(lo, nask);
		lo = nask + 1;
	}
	sort(all(qs));
	ll res = 0;
	rep(i,0,sz(qs) - 1) res = max(res, qs[i + 1] - qs[i]);
	return res;
}

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