Submission #1199718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199718		shjeong	Gap (APIO16_gap)	C++20	0 / 100	44 ms	2668 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
long long findGap(int T, int N)
{
    ll ret = 0;
    if(T==1){
        vector<ll> v1, v2;
        ll mn= 0, mx = 1e18;
        while(mn<=mx){
            ll MN, MX;
            MinMax(mn,mx,&MN,&MX);
            if(MN<0)break;
            v1.push_back(MN); v2.push_back(MX);
            mn=MN+1,mx=MX-1;
        }
        reverse(all(v2));
        for(auto i : v2)v1.push_back(i);
        for(int i = 1 ; i < sz(v1) ; i++)ret=max(ret,v1[i]-v1[i-1]);
    }
    else{
        ll mn=0, mx=1e18;
        ll MN, MX;
        MinMax(mn,mx,&MN,&MX);
        if(N==2)return MX-MN;
        ll t = (MX-MN+N-2)/(N-1);
        vector<ll> v;
        mn=MN,mx=MX;
        for(ll i = mn+1 ; i < mx ; i+=t){
//            cout<<i<<endl;
            MinMax(i,i+t-1,&MN,&MX);
            if(MN>=0){
                if(sz(v))ret=max(ret, MN-v.back());
                v.push_back(MX);
            }
        }
    }
	return ret;
}

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