Submission #338710

#	Time	Username	Problem	Language	Result	Execution time	Memory
338710		bigDuck	Gap (APIO16_gap)	C++14	89.04 / 100	68 ms	1260 KiB

gap

#include "gap.h"

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll


int n;
int l1, r1;
int subtask_1(){

int l=-2, r=(1e18); r+=1;
int mx=1;
int cnt=0;
while(cnt<n){

    MinMax(l+1, r-1, &l1, &r1);
    if( (cnt>0)  ){
        mx=max(max((ll)l1-l, (ll)r-r1), mx );
    }
    cnt+=2;
    l=l1, r=r1;
    //cout<<l<<" "<<r<<"\n"<<flush;
}
mx=max(mx, r-l);
return mx;
}





int subtask_2(){


int ft, lt;
MinMax(0, 1e18, &ft, &lt);

int d=(lt-ft)/n;
int res=0;
int l=-1, r=ft;
int l1=-1, r1=-1;
for(int i=ft+1; i<lt; i+=d){
    MinMax(i, min(i+d-1, lt-1), &l1, &r1);

    if(r>=0){res=max(res, l1-r );}
    l=max(l1, l); r=max(r1, r);
}
res=max(res, lt-r);
return res;

}








long long findGap(int32_t T, int32_t N)
{
    n=N;
    if(T==1){
        return subtask_1();
    }
    else{
        return subtask_2();
    }
}

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