Submission #503964

#	Time	Username	Problem	Language	Result	Execution time	Memory
503964		Carmel_Ab1	Gap (APIO16_gap)	C++17	100 / 100	106 ms	11988 KiB

gap

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

typedef long long ll;
typedef vector<ll> vl;

#define all(x) x.begin(),x.end()
#define pb push_back

ll ceil(ll a,ll b){return (a+b-1)/b;}
ll findGap(int T, int n){
    ll L=0,R=1e18;

    vl a;
    if(T==1){
        int i=0;
        while(2*i<n){
            MinMax(L,R,&L,&R);
            a.pb(L);
            a.pb(R);
            L++,R--;
            i++;
        }
        if(L==R && L!=-1)
            a.pb(L);
        ll ans=0;
        sort(all(a));
        for(int i=0; i+1<a.size(); i++)
            ans=max(ans,a[i+1]-a[i]);
        return ans;
    }
    MinMax(0,1e18,&L,&R);

    ll block=ceil(R-L+1,n);


    ll ans=0;
    multiset<ll>s={L};
    a={L,R};

    for(int i=0; i<n; i++){
        ll l=max(L+1,L+i*block);
        ll r=min(R-1,l+block-1);

        if(i==n-1)
            s.insert(R);
        while(l<r){
            MinMax(l,r,&l,&r);
            if(l==-1)break;
            a.pb(l);
            a.pb(r);
            s.insert(l);
            s.insert(r);

            ans=max(ans,r-(*(--s.lower_bound(r))));
            if(s.upper_bound(l)!=s.end())
                ans=max(ans,*s.upper_bound(l)-l);
            l++,r--;

            if(r-l<=ans)break;
        }
        if(l==r && l!=-1)
            a.pb(l);
    }


    sort(all(a));
    for(int i=0; i+1<a.size(); i++)
        ans=max(ans,a[i+1]-a[i]);
    return ans;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:29:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0; i+1<a.size(); i++)
      |                      ~~~^~~~~~~~~
gap.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0; i+1<a.size(); i++)
      |                  ~~~^~~~~~~~~

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