제출 #548075

#제출 시각아이디문제언어결과실행 시간메모리
548075SamNguyenGap (APIO16_gap)C++14
30 / 100
96 ms7012 KiB
#include "gap.h" #include <vector> #include <iostream> #include <random> #include <algorithm> using namespace std; const long long INF = 1e18; mt19937_64 rnd(23478612); inline long long random(long long MIN, long long MAX) { return rnd() % (MAX - MIN + 1) + MIN; } long long calc_cost(const vector<long long> &seq) { long long res = 0; for (int i = 0; i + 1 < (int)seq.size(); i++) res = max(res, seq[i + 1] - seq[i]); return res; } namespace SUB1 { long long findGap(int N) { vector<long long> seq(N); long long L = 0, R = INF; for (int i = 0, j = N - 1; i <= j; i++, j--) { MinMax(L, R, &seq[i], &seq[j]); L = seq[i] + 1, R = seq[j] - 1; } return calc_cost(seq); } } namespace SUB2 { long long findGap(int N) { vector<long long> marks = {0}; for (int i = 0; i < 2 * N; i++) marks.push_back(random(1, INF)); marks.push_back(INF + 1); sort(marks.begin(), marks.end()); vector<pair<long long, long long>> rep; for (int i = 0; i + 1 < (int)marks.size(); i++) { long long l, r; MinMax(marks[i], marks[i + 1], &l, &r); rep.emplace_back(l, r); } long long ans = 0; for (int i = 0; i + 1 < (int)marks.size(); i++) { ans = max(ans, rep[i + 1].first - rep[i].second); } return ans; } } long long findGap(int T, int N) { return (T == 1) ? SUB1::findGap(N) : SUB2::findGap(N); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...