Submission #1075882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075882		alexdd	Gap (APIO16_gap)	C++17	100 / 100	42 ms	2868 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
pair<int,int> qry(int le, int ri)
{
    pair<int,int> aux;
    MinMax(le,ri,&aux.first,&aux.second);
    return aux;
}
long long bigsolve(int N)
{
    pair<int,int> tot = qry(0,INF);
    int cur=tot.first;
    int rez = (tot.second-tot.first-1)/(N-1)+1;
    while(tot.second - cur > rez)
    {
        pair<int,int> aux = qry(cur+1,cur+rez);
        if(aux.first!=-1)
        {
            cur = aux.second;
            continue;
        }
        int c=rez;
        while(1)
        {
            c=(c+1)*2;
            aux = qry(cur+1,cur+c);
            if(aux.first!=-1)
            {
                rez = max(rez, aux.first - cur);
                cur = aux.second;
                break;
            }
        }
    }
    return rez;
}
int smallsolve(int N)
{
    pair<int,int> tot = qry(0,INF);
    int le=tot.first,ri=tot.second,rez=1,pozle=1,pozri=N;
    while(ri-le > rez)
    {
        if(pozle+1>=pozri)
        {
            rez = max(rez, ri-le);
            break;
        }
        pair<int,int> aux = qry(le+1,ri-1);
        rez = max(rez, aux.first-le);
        rez = max(rez, ri-aux.second);
        le = aux.first;
        ri = aux.second;
        pozle++;
        pozri--;
    }
    return rez;
}
long long findGap(int32_t T, int32_t N)
{
    if(T==1) return smallsolve(N);
    return bigsolve(N);
}

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