Submission #1169933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169933		trandangquang	Gap (APIO16_gap)	C++20	100 / 100	40 ms	2240 KiB

gap

#include"gap.h"

#include<bits/stdc++.h>
using namespace std;

#define ll long long 

// void MinMax(ll s, ll t, ll &mn, ll &mx){
//     vector<int> a={2,3,6,8};
//     mn=*lower_bound(a.begin(),a.end(),s); 
//     mx=*(upper_bound(a.begin(),a.end(),t)-1);
//     if(mn>mx) mn=mx=-1;
// }

ll findGap(int t, int n){
    if(t==1){
        ll mi=1, mx=1e18;
        
        vector<ll> a;
        for(int i=0; i<(n+1)/2; ++i){
            ll l,r;
            MinMax(mi,mx,&l,&r);
            a.emplace_back(l); a.emplace_back(r);
            mi=l+1,mx=r-1;
        }
        sort(a.begin(),a.end());
        
        ll res=0;
        for(int i=1;i<a.size();++i){
            res=max(res,a[i]-a[i-1]);      
        }
        return res;
    }    
    else{
        ll mi=1,mx=1e18;
        MinMax(1,(ll)1e18,&mi,&mx);
        ll gap=(mx-mi+n-2)/(n-1), l=mi, res=gap;
        for(ll i=mi; i<=mx; i+=gap+1){
            ll x,y;
            MinMax(i,i+gap,&x,&y);
            if(x!=-1){
                res=max(res,x-l);
                l=y;
            } 
        }     
        return res;
    }
}

// int main(){
//     cout<<findGap(2,4);
// }

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