제출 #609672

#제출 시각아이디문제언어결과실행 시간메모리
609672AugustinasJucasGap (APIO16_gap)C++14
8.56 / 100
159 ms6980 KiB
#include <bits/stdc++.h> #include "gap.h" using namespace std; int n; set<long long> setas; long long rnd(long long L, long long R) { long long sk = rand() % 1000000007ll; sk = sk * (rand() % 1000000007ll); return L + sk % (R - L + 1); } void calc(long long L, long long R) { if(L > R) return ; long long mn, mx; MinMax(L, R, &mn, &mx); if(mn == -1) return ; long long mid = rnd(L, R); long long MX = mx; long long sk = -1; MinMax(mid, R, &mn, &mx); if(mn == -1) { sk = MX; calc(L, MX-1); }else { sk = mn; calc(L, sk-1); calc(mid+1, mx-1); setas.insert(mx); } setas.insert(sk); } long long findGap(int T, int N) { srand(time(0)); n = N; long long L = 0, R = 1e18; calc(L, R); vector<long long> mas; for(auto x : setas) mas.push_back(x); long long ans = 0; for(int i = 0; i < n-1; i++) { ans = max(ans, mas[i+1] - mas[i]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...