Submission #240545

#	Time	Username	Problem	Language	Result	Execution time	Memory
240545		Dremix10	Gap (APIO16_gap)	C++17	100 / 100	64 ms	2424 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
//#define N (int)(1e5+1)




long long findGap(int T, int N){
    if(T==1){
        int i;
        vector<ll> arr;
        ll limit=(N+1)/2;

        ll l=1,r=1e18+1;

        while(arr.size()<N){
            ll mini,maxi;
            ll* p1 = &mini;
            ll* p2 = &maxi;
            MinMax(l,r,p1,p2);
            arr.push_back(mini);
            if(arr.size()<N)
                arr.push_back(maxi);
            l=mini+1;
            r=maxi-1;
        }
        sort(arr.begin(),arr.end());

        ll ans=0;
        for(i=0;i<N-1;i++)
            ans=max(ans,arr[i+1]-arr[i]);
        return ans;
    }

    int i;
    ll low,high;
    MinMax(0,(ll)1e18,&low,&high);

    ll range=high-low+1;
    ll ans=range/N;
    if(range%N)
        ans++;

    ll nxt=low+1;
    ll prev=low;
    while(nxt<=high){
        ll mini,maxi;
        MinMax(nxt,nxt+ans,&mini,&maxi);
        nxt+=ans+1;
        if(mini==-1){
        //    nxt+=ans+1;
            continue;
        }

        ans=max(ans,mini-prev);
        prev=maxi;

    }
    return ans;


}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(arr.size()<N){
               ~~~~~~~~~~^~
gap.cpp:33:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(arr.size()<N)
                ~~~~~~~~~~^~
gap.cpp:23:12: warning: unused variable 'limit' [-Wunused-variable]
         ll limit=(N+1)/2;
            ^~~~~
gap.cpp:46:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^

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