Submission #1207397

#TimeUsernameProblemLanguageResultExecution timeMemory
1207397jasonicGap (APIO16_gap)C++20
89.04 / 100
39 ms3008 KiB
#include "gap.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define fastIO cin.tie(0); ios::sync_with_stdio(false) const ll MINN = 0; const ll MAXN = 1e18; ll solve1(int N) { ll mn = MINN, mx = MAXN; queue<ll> left; stack<ll> right; while(true) { ll l, r; MinMax(mn, mx, &l, &r); if(l == r) { left.push(l); } else { left.push(l); right.push(r); } mn = l + 1; mx = r - 1; if(left.size() + right.size() == N) break; } vector<ll> a; while(!left.empty()) { a.push_back(left.front()); left.pop(); } while(!right.empty()) { a.push_back(right.top()); right.pop(); } ll ans = 0; for(int i = 1; i < N; i++) { ans = max(ans, a[i] - a[i-1]); } return ans; } ll solve2(int N) { ll rangeL, rangeR; MinMax(0, MAXN, &rangeL, &rangeR); ll step = ( (rangeR - rangeL) - N - 1) / (N - 1); ll ans = step, x, y, l = rangeL, i; for(i = rangeL + 1; i < rangeR; i += step + 1) { MinMax(i, min(i + step, rangeR), &x, &y); if(x != -1) { ans = max(ans, x - l); l = y; } } return ans; } ll findGap(int T, int N) { if(T == 1) { return solve1(N); } else if(T == 2) { return solve2(N); } return 42; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...