제출 #464750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464750		nickmet2004	Gap (APIO16_gap)	C++11	83.51 / 100	63 ms	1180 KiB

gap

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

ll findGap(int T , int n){
    ll x = 0 , y = 1e18 ,mn , mx , ans = 0;
    if(T == 1){
        MinMax(x , y , &mn , &mx);
        x = mn , y = mx;
        for(int i = 1; i < (n + 1) /2; ++i){
            MinMax(x+1 , y-1 , &mn , &mx);
            ans = max({ans, y - mx , mn - x});
            x = mn , y =mx;
        }
    return max(ans , mx-mn);
    }
     //1 2 3 4 5 6
    MinMax(0 , 1e18 , &mn , &mx);
    ll sz = ans = (mx- mn-1) / (n - 1);
    x = mn , y = mx;
    if((x - y + 1) / n == 1)return 1;
    //1  4  6 30
    ll lst = 1e18;
    for(ll i = x-1; i < y; i += sz){
        MinMax(i+1 , i + sz , &mn , &mx);
        if(mn == -1)continue;
        ans = max(ans , mn - lst);
        lst = mx;
    }
    return ans;
}

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