제출 #1192532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192532		Gray	Gap (APIO16_gap)	C++20	100 / 100	44 ms	2328 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)1e18
ll MOD = 1e9+7;


long long findGap(int T, int N)
{

    if (T==1){
        ll l, r; MinMax(0, 1e18, &l, &r);
        vector<ll> vals = {l, r};
        while ((ll)vals.size()<N){
            MinMax(l+1, r-1, &l, &r);
            vals.push_back(l);
            if(l!=r) vals.push_back(r);
        }
        sort(vals.begin(), vals.end());
        ll res=0;
        for (ll i=1; i<(ll)vals.size(); i++){
            res=max(res, vals[i]-vals[i-1]);
        }
        return res;
    }else {
        ll l, r; MinMax(0, 1e18, &l, &r);
        // cout << l << " " << r << endl;
        ll md = (r-l-1)/(N-1);
        ll res=0;
        for (ll i=l+1; i<r;){
            ll to = i-1;
            ll mn=-1, mx=-1;
            while (mn==-1){
                to+=2*md;
                MinMax(i, to, &mn, &mx);
            }
            res=max(res, mn-i);
            i=mx+1;
            // cout << i << endl;
        }
        return res+1;
    }
}

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