Submission #941635

#TimeUsernameProblemLanguageResultExecution timeMemory
941635shoryu386A Difficult(y) Choice (BOI21_books)C++17
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; typedef long long ll; long long gA, gK; void recur(int x, int taken, ll sum, vector<pair<int, ll>> takeitem, vector<pair<int, ll>> &items){ if (x == items.size()){ if (taken == gK && gA <= sum && sum <= 2LL*gA){ vector<int> indices; for (int x = 0; x < (int)takeitem.size(); x++){ indices.push_back(items[x].first); } answer(indices); return; } return; } recur(x+1, taken, sum, takeitem, items); if (taken != gK){ takeitem.push_back(items[x]); recur(x+1, taken+1, sum+items[x].second, takeitem, items); } } void solve(int N, int K, long long A, int S) { // TODO implement this function //k books, sum of A //x, x+1, x+2, x+3, x+4, x+5... and so on gA = A; gK = K; int extrasum = 0; for (int x = 0; x < K; x++){ extrasum += x; } //we want A <= x*K + extrasum <= 2*A //x*K + extrasum >= A //x*K >= A-extrasum //x >= (A-extrasum)/K ll target = (A - extrasum)/K + ((A - extrasum)%K != 0); //to do: check rounding if (A - extrasum <= 0) {impossible(); return;} int l = 1, r = N+1-K, ans = N+1-K; while (l <= r){ int m = (l+r)/2; ll res = skim(m); if (res >= target){ r = m-1; ans = m; } else{ l = m+1; } } vector<pair<int, ll>> items; set<int> indicesInside; for (int x = max(1, ans-10); x < min(N+1, ans+K); x++){ items.push_back({x, skim(x)}); indicesInside.insert(x); } for (int x = 1; x <= 10; x++){ if (indicesInside.count(x) == 0) items.push_back({x, skim(x)}), indicesInside.insert(x); } recur(0, 0, 0, {}, items); impossible(); }

Compilation message (stderr)

books.cpp: In function 'void recur(int, int, ll, std::vector<std::pair<int, long long int> >, std::vector<std::pair<int, long long int> >&)':
books.cpp:11:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  if (x == items.size()){
      |      ~~^~~~~~~~~~~~~~~
#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...