Submission #835687

#	Time	Username	Problem	Language	Result	Execution time	Memory
835687		Khizri	Gap (APIO16_gap)	C++17	100 / 100	39 ms	2256 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
long long findGap(int test, int n)
{
    if(test==1){
        ll l=0,r=1e18;
        vector<ll>vt;
        while(vt.size()<n){
            ll a=0,b=0;
            MinMax(l,r,&a,&b);
            //if(b==-1) break;
            if(a!=b){
                vt.pb(a);
                vt.pb(b);
            }
            else{
                vt.pb(a);
            }
            l=a+1,r=b-1;
        }
        sort(vt.begin(),vt.end());
        ll ans=0;
        for(int i=1;i<vt.size();i++){
            ans=max(ans,vt[i]-vt[i-1]);
        }
        return ans;
    }
	ll l=0,r=0;
    MinMax(0ll,(ll)(1e18),&l,&r);
    ll res=(r-l)/(n-1);
    ll ans=(r-l)/(n-1);
    while(l<r){
        ll a=0,b=0;
        MinMax(l+1,l+res+1,&a,&b);
        if(b==-1){
            res+=res;
        }
        else{
            ans=max(ans,a-l);
            l=b;
            res=ans;
        }
    }
    return ans;
}
/*
g++ gap.cpp grader.cpp ; .\a.exe
*/

Compilation message (stderr)

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

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