| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1304712 | kindep | Gap (APIO16_gap) | C++20 | 0 ms | 0 KiB |
//Reaktor Osemkowo Wodny - Kinga Deptula
#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);
}
*/
