제출 #1287562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287562		khoavn2008	Gap (APIO16_gap)	C++17	70 / 100	47 ms	3232 KiB

gap

#ifndef KHOA
#include "gap.h"
#endif // KHOA

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(int i = 0, _r = (r); i < _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 2e5 + 10, INF = 2e18, LOG = 21;
ll a[N];

#ifdef KHOA
ll A[N] = {-2008, };
void MinMax(ll x,ll y,ll *z,ll *t){
    bool ok = 0;
    FOR(i,1,10){
        if(x <= a[i] && !ok){
            *z = a[i];
            ok = 1;
        }
        if(a[i] <= y)*t = a[i];
    }
}
#endif

ll findGap(int T, int n){
    ll mi,mx,v1,v2;
		MinMax(0,1e18,&mi,&mx);
		if(n==2)
			return mx-mi;
			// [mi+1,mx-1]
			// mx-mi-1
		ll len=(mx-mi+n-1)/(n-1);
		ll last=mi,ans=0;;
		for(ll cmi=mi+1,cmx=mi+len,i=1;i<n;i++,cmi+=len,cmx+=len)
		{
			if(cmx>=mx)cmx=mx-1;
			if(cmi<=cmx)
			{
				MinMax(cmi,cmx,&v1,&v2);
				if(v1!=-1)
				{
					ans=max(ans,v1-last);
					last=v2;
				}
			}
			else{
				break;
			}
		}
		ans=max(ans,mx-last);
		return ans;
}

#ifdef KHOA
int main(){
    FOR(i,1,10)a[i] = i * 10,cerr<<a[i]<<' ';
    cerr<<endl;
    cout<<findGap(1, 10);

}
#endif

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