제출 #414052

#제출 시각아이디문제언어결과실행 시간메모리
414052Tc14A Difficult(y) Choice (BOI21_books)C++17
60 / 100
2 ms292 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include "books.h" using namespace std; #define ve vector typedef long long ll; typedef pair<int, int> pii; const int INF = 1e9 + 10; map<int, ll> M; ll B(int i) { if (M.find(i) == M.end()) M[i] = skim(i + 1); return M[i]; } void solve(int n, int k, ll a, int s) { int lo = 0; int hi = n - 1; while (lo < hi) { int m = (lo + hi) / 2; if (B(m) >= a) hi = m; else lo = m + 1; } int z = lo; ll x = B(z); if (x >= a) { if (z >= k - 1) { ll sum = x; ve<int> I(k); I[k - 1] = z + 1; for (int i = 0; i < k - 1; i++) { sum += B(i); I[i] = i + 1; } if (sum <= 2 * a) { answer(I); return; } } } else z = n; if (z >= k) { ll sum = 0; ve<int> I(k); for (int i = 0; i < k; i++) { sum += B(i); I[i] = i + 1; } for (int i = k - 1; i >= 0; i--) { hi = z - k + i; lo = i; sum -= B(i); if (sum + B(hi) >= a) { while (lo < hi) { int m = (lo + hi) / 2; if (sum + B(m) < a) lo = m + 1; else if (sum + B(m) > 2 * a) hi = m; else { I[i] = m + 1; answer(I); return; } } if (a <= sum + B(lo) && sum + B(lo) <= 2 * a) { I[i] = lo + 1; answer(I); return; } } else { sum += B(hi); I[i] = hi + 1; } } } impossible(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...