제출 #1003472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003472		amine_aroua	Gap (APIO16_gap)	C++17	100 / 100	42 ms	2824 KiB

gap

#include <bits/stdc++.h>
using namespace std;
#define intt long long
#define fore(i , n) for(int i = 0 ; i < n; i++)
#define forr(i , x ,y) for(int i = x;  i <= y;i++)
#define pb push_back
void MinMax(intt s , intt t , intt *mn , intt *mx);
long long findGap(int T, int N)
{
    if(T == 1)
    {
        intt mn = 0 , mx = 1e18*1LL;
        vector<intt> a;
        int n = N;
        while(n)
        {
            MinMax(mn , mx , &mn , &mx);
            a.pb(mn);
            n--;
            if(mn == mx)
                break;
            a.pb(mx);
            n--;
            mn++;
            mx--;
        }
        sort(a.begin() , a.end());
        intt ans = 0;
        fore(i , N - 1)
        {
            ans = max(ans , a[i + 1] - a[i]);
        }
        return ans;

    }
    intt mn , mx;
    MinMax(0ll , 1LL * 1e18 , &mn , &mx);
    intt gmn = mn , gmx = mx;
    intt d = (mx - mn + N - 2)/((N - 1));
    vector<intt> MinB(N , -1) , MaxB(N , -1);
    fore(i , N - 1)
    {
        intt lt = i * d + gmn , rt = (i + 1)*d + gmn - 1;
        MinMax(lt , rt , &mn , &mx);
        MinB[i] = mn;
        MaxB[i] = mx;
    }
    if((N - 1) * d + gmn <= gmx)
        MinB[N - 1]= MaxB[N - 1] = gmx;
    intt prv = MaxB[0];
    intt ans = (intt)d;
    forr(i , 1 , N - 1)
    {
        if(MinB[i] == -1)
            continue;
        ans = max(ans , MaxB[i] - MinB[i]);
        ans=  max(ans , MinB[i] - prv);
        prv = MaxB[i];
    }
    return ans;
}

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