제출 #255787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255787		Osama_Alkhodairy	Gap (APIO16_gap)	C++17	70 / 100	73 ms	2864 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

ll findGap(int T, int N){
    ll mn, mx;
    if(T == 1){
        MinMax(0, 1e18, &mn, &mx);
        ll ans = 0;
        while(mn + 1 < mx){
            ll new_mn, new_mx;
            MinMax(mn + 1, mx - 1, &new_mn, &new_mx);
            if(new_mn == -1){
                ans = max(ans, mx - mn);
            }
            ans = max(ans, new_mn - mn);
            ans = max(ans, mx - new_mx);
            mn = new_mn;
            mx = new_mx;
        }
        if(mn != mx) ans = max(ans, mx - mn);
        return ans;
    }
    MinMax(0, 1e18, &mn, &mx);
    ll l = mn, r = mx;
    ll g = (r - l - (N - 2)) / (N - 1);
    ll cur_l = l;
    vector <ll> mnq, mxq;
    for(int i = 0 ; cur_l < r ; i++){
        ll sz = g + (i < (r - l - (N - 2)) % (N - 1));
        ll cur_r = cur_l + sz;
        MinMax(cur_l, cur_r, &mn, &mx);
        if(mn != -1){
            mnq.push_back(mn);
            mxq.push_back(mx);
        }
        cur_l += sz + 1;
    }
    ll ans = (r - l + N - 2) / (N - 1);
    for(int i = 1 ; i < (int)mnq.size() ; i++){
        ans = max(ans, mnq[i] - mxq[i - 1]);
    }
    return ans;
}

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