제출 #850785

#제출 시각아이디문제언어결과실행 시간메모리
850785d4xnA Difficult(y) Choice (BOI21_books)C++17
0 / 100
1 ms1368 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; #define ll long long const ll N = 1e5+5; ll dp[N]; void solve(int N, int K, long long A, int S) { memset(dp, -1, sizeof(dp)); ll l = 1; ll r = N; while (l < r) { ll mid = (l+r)>>1; if (dp[mid] == -1) dp[mid] = skim(mid); if (dp[mid] < A) l = mid+1; else r = mid; } if (dp[l] == -1) dp[l] = skim(l); vector<int> test; test.push_back(l); ll cnt = dp[l]; for (ll i = 1; i <= K-1; i++) { if (dp[i] == -1) dp[i] = skim(i); cnt += dp[i]; cerr << cnt << endl; test.push_back(i); } if (K-1 < l && A <= cnt && cnt <= A*2) { answer(test); return; } if (K >= l) { impossible(); return; } cnt = 0; vector<int> ans; for (ll i = 1; i <= K; i++) { if (dp[i] == -1) dp[i] = skim(i); cnt += dp[i]; ans.push_back(i); } if (cnt > 2*A) { impossible(); return; } for (ll i = l-1; i >= l-K; i--) { if (dp[i] == -1) dp[i] = skim(i); } ll curr = 0; r = l-1; while (curr < K && cnt < A) { cnt -= dp[curr+1]; cnt += dp[r]; ans[curr] = r; curr++; r--; } if (cnt >= A && cnt <= A*2) answer(ans); 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...