Submission #1304719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304719		kindep	Gap (APIO16_gap)	C++20	100 / 100	48 ms	3236 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
using namespace std;
constexpr long long INF=1e18;
vector<long long> vec;

/*
void MinMax(long long s, long long t, long long &mn, long long &mx){
    auto it=lower_bound(vec.begin(), vec.end(), s);
    if ((it==vec.end())||(*it>t)){
        mn=mx=-1; return;
    }
    auto it2=upper_bound(vec.begin(), vec.end(), t);
    if (it2!=vec.begin())
        it2--;
    mn=*it, mx=*it2;
    return;
}
    */

void podzad1(int N, long long &wyn){
    long long t[N+1], mn=INF, mx=0;
    MinMax(0, INF, &mn, &mx);
    t[1]=mn, t[N]=mx;
    for (int i=2; i<=(N+1)/2; i++){
        mn=INF, mx=0;
        MinMax(t[i-1]+1, t[N-(i-2)]-1, &mn, &mx);
        t[i]=mn, t[N-(i-1)]=mx;
    }
    for (int i=1; i<N; i++){
        wyn=max(wyn, t[i+1]-t[i]);
    }
    return;
}

void podzad2(int N, long long &wyn){
    long long n=N;
    vector<long long> war;
    long long pier=INF, ost=0, prz, pom;
    MinMax(0, INF, &pier, &ost);
    war.push_back(pier);
    if (n<=2){
        wyn=ost-pier;
        return;
    }
    prz=(ost-pier)/(n-1);
    for (long long i=pier+1LL; i+prz<=ost; i+=prz+1LL){
        long long a=INF, b=0;
        MinMax(i, i+prz, &a, &b);
        pom=i+prz+1;
        if ((a!=(long long)(-1))&&(a!=b))
            war.push_back(a), war.push_back(b);
        else if (a!=(long long)(-1))
            war.push_back((a));
    }
    long long a=INF;
    MinMax(pom, max(pom, ost), &a, &ost);
    war.push_back(a);
    war.push_back(ost);
    for (int i=1; i<war.size(); i++){
        wyn=max(wyn, war[i]-war[i-1]);
    }
    return;
}


long long findGap(int T, int N){
    long long wyn=0;
    if (T==1)
        podzad1(N, wyn);
    else
        podzad2(N, wyn);
    return wyn;
}


/*
int main(){
    int T, N; long long a, pom=0; cin >> T >> N;
    for (int i=0; i<N; i++){
        cin >> a, vec.push_back(a);
        if (i)
            pom=max(pom, vec[i]-vec[i-1]);
    }
    cout << findGap(T, N);
    cout << pom;
}
*/

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