Submission #1101391

#TimeUsernameProblemLanguageResultExecution timeMemory
1101391MateiKing80A Difficult(y) Choice (BOI21_books)C++14
100 / 100
2 ms1276 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; void solve(int N, int K, long long A, int S) { vector<ll> x(N + 1); ll sum = 0; for(int i = 1; i <= K; i ++) sum += x[i] = skim(i); if(sum > 2 * A) impossible(); sum -= x[K]; int l = K + 1, h = N, a = N + 1; while(l <= h) { int mid = (l + h) / 2; if(skim(mid) >= A) { h = mid - 1; a = mid; } else l = mid + 1; } if(a != N + 1) { sum += x[a] = skim(a); if(sum <= 2 * A) { vector<int> ans; for(int i = 1; i < K; i ++) ans.push_back(i); ans.push_back(a); answer(ans); return; } } for(int i = 0; i < K; i ++) x[a - i - 1] = skim(a - i - 1); for(int i = 0; i <= K; i ++) { sum = 0; vector<int> ans; for(int j = 1; j <= K - i; j ++) { sum += x[j]; ans.push_back(j); } for(int j = 0; j < i; j ++) { sum += x[a - j - 1]; ans.push_back(a - j - 1); } if(sum >= A && sum <= 2 * A) { answer(ans); return; } } 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...