제출 #21917

#제출 시각아이디문제언어결과실행 시간메모리
21917sampritiGap (APIO16_gap)C++14
70 / 100
76 ms7460 KiB
#include "gap.h" #include <climits> #include <vector> using namespace std; long long binary_solve(long long L, long long R) { if(R - L <= 1) return R - L; int mid = (L + R)/2; long long qL1, qR1; MinMax(L + 1, mid, &qL1, &qR1); long long qL2, qR2; MinMax(mid + 1, R - 1, &qL2, &qR2); if(qL1 == -1 && qL2 == -1) return R - L; long long ans = 0; if(qL1 != -1 && qL2 != -1) ans = max(ans, qL2 - qR1); if(qL1 != -1) { ans = max(ans, qL1 - L); ans = max(ans, binary_solve(qL1, qR1)); } if(qL2 != -1) { ans = max(ans, R - qR2); ans = max(ans, binary_solve(qL2, qR2)); } return ans; } long long findGap(int T, int N) { long long L, R; MinMax(0, LLONG_MAX, &L, &R); if(T == 1) { return binary_solve(L, R); } long long diff = ((R - L - 1) + (N - 2))/(N - 1); vector<pair<long long, long long> > cands; cands.push_back({L, L}); for(long long x = L + 1; x <= R - 1; x += diff) { long long qL, qR; MinMax(x, min(x + diff - 1, R - 1), &qL, &qR); if(qL != -1) cands.push_back({qL, qR}); } cands.push_back({R, R}); long long ans = 0; for(int i = 1; i < cands.size(); i++) { ans = max(ans, cands[i].first - cands[i - 1].second); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < cands.size(); i++) {
                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...