Submission #678483

#	Time	Username	Problem	Language	Result	Execution time	Memory
678483		cig32	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	124 ms	336 KiB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;
void solve(int N, int K, long long A, int S) {
  int lb = 1, rb = N;
  while(lb < rb) {
    int mid = (lb + rb) >> 1;
    if(skim(mid) >= A ) rb = mid;
    else lb = mid + 1;
  }
  vector<pair<int, long long> > vt;
  for(int i=1; i<=min(K, lb); i++) vt.push_back({i, skim(i)});
  for(int i=max(min(K, lb) + 1, lb-K); i<=lb; i++) vt.push_back({i, skim(i)});
  int M = vt.size();
  for(int i=0; i<(1<<M); i++) {
    long long s = 0;
    for(int j=0; j<M; j++) if(i & (1<<j)) s += vt[j].second;
    if(s >= A && s <= 2*A && __builtin_popcount(i) == K) {
      vector<int> fin;
      for(int j=0; j<M; j++) if(i & (1<<j)) fin.push_back(vt[j].first);
      answer(fin); return;
    }
  }
  impossible();
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20