Submission #1304713

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

gap

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

/*
void ZapytajChrisa(long long s, long long t, long long &mn, long long &mx){
    cout << "POMIEDZY: " << s << " " << t << '\n';
    cin >> mn >> mx;
    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;
    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);
        if ((a!=-1)&&(a!=b))
            war.push_back(a), war.push_back(b);
        else if (a!=-1)
            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; cin >> T >> N;
    cout << ZnajdzSkarpe(T, N);
}
*/

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