Submission #625936

#	Time	Username	Problem	Language	Result	Execution time	Memory
625936		socpite	Gap (APIO16_gap)	C++14	70 / 100	58 ms	3228 KiB

gap

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

#define f first
#define s second

typedef long long ll;


long long findGap(int T, int N)
{
    ll l, r, ans = 0, n = N;
    MinMax(0, 1e18, &l, &r);
    if(T==1){
        while(l < r){
            if(r==l+1){
                ans = max(ans, 1LL);
                break;
            }
            ll nxtl, nxtr;
            MinMax(l+1, r-1, &nxtl, &nxtr);
            if(nxtl >= 0){
                ans = max(ans, nxtl-l);
                ans = max(ans, r-nxtr);
            }
            else{
                ans = max(ans, r-l);
            }
            l = nxtl;
            r = nxtr;
        }
    }
    else{
        vector<pair<ll, ll>> vec;
        ll dist = (r-l-1)/n + !!((r-l-1)%n);
        for(ll i = l+1; i < r; i+=dist){
            ll rb = min(r-1, i+dist-1);
            pair<ll, ll> tmp;
            MinMax(i, rb, &tmp.f, &tmp.s);
            if(tmp.f >= 0)vec.push_back(tmp);
        }
        if(vec.empty())ans = r-l;
        else{
            ans = max(vec[0].f - l, r-vec.back().s);
            for(int i = 1; i < vec.size(); i++){
                ans = max(ans, vec[i].f - vec[i-1].s);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

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

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