제출 #398263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398263		tengiz05	Gap (APIO16_gap)	C++17	30 / 100	73 ms	3260 KiB

gap

#ifndef EVAL
#include "grader.cpp"
#endif
#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll findGap(int T, int n){
	if(T == 1){
		ll ans = 0;
		ll l=0, r=1e18;
		vector<ll> a(n+1);
		ll mn, mx;
		int idl = 1, idr = n;
		while(idl <= idr){
			MinMax(l, r, &mn, &mx);
			a[idl] = mn;
			a[idr] = mx;
			l = mn+1, r = mx-1;
			idl++;
			idr--;
		}
		for(int i=2;i<=n;i++)ans = max(ans, a[i]-a[i-1]);
		return ans;
	}else {
		ll l=0, r=1e18;
		MinMax(l,r,&l,&r);
		//~ if(r-l+1 == n){
			//~ return 1;
		//~ }
		vector<pair<ll,ll>> v;
		ll len = (r-l-n)/n;
		ll nl=l, nr=l+len;
		for(ll i=0;i<n;i++){
			v.push_back({nl, nr});
			nl += len+1, nr += len+1;
		}v[v.size()-1].second = r;
		//~ for(auto [x,y] : v){cout << x << ' ' << y << '\n';}cout << '\n';
		ll ans = len;
		ll last = 1e18;
		for(auto [x,y] : v){
			ll mn=0, mx=1e18;
			MinMax(x,y,&mn,&mx);
			ans = max(ans, mn - last);
			last = mx;
		}
		return ans;
	}
}

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