Submission #1280881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280881		StefanSebez	Gap (APIO16_gap)	C++20	100 / 100	44 ms	3236 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
const ll inf=1e18;
void chmx(ll &x,ll y){x=max(x,y);}
void Unique(vector<ll>&a){sort(a.begin(),a.end());int m=unique(a.begin(),a.end())-a.begin();a.resize(m);}
pair<ll,ll> Query(ll l,ll r){
    if(l>r) return {-1,-1};
    ll L,R;
    MinMax(l,r,&L,&R);
    return {L,R};
}
long long findGap(int T, int n){
    if(T==2){
        auto [L,R]=Query(0,inf);
        ll res=(R-L+n-2)/(n-1);
        vector<ll>temp={L,R};
        for(ll i=0;i<n-1;i++){
            auto [l,r]=Query(L+i*res,min(L+(i+1)*res-1,R));
            if(l==-1) continue;
            temp.pb(l);temp.pb(r);
        }
        Unique(temp);
        for(int i=1;i<temp.size();i++) chmx(res,temp[i]-temp[i-1]);
        return res;
    }
    if(T==1){
        vector<ll>a(n+1);
        for(ll i=1,j=n,l=0,r=1e18;i<=j;i++,j--){
            MinMax(l,r,&a[i],&a[j]);
            l=a[i]+1,r=a[j]-1;
        }
        ll res=0;
        for(int i=2;i<=n;i++) res=max(res,a[i]-a[i-1]);
        return res;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^

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