Submission #553993

#	Time	Username	Problem	Language	Result	Execution time	Memory
553993		Sam_a17	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	42 ms	460 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int M = 1e5 + 10;
long long a[M];
 
void solve(int N, int K, long long A, int S) {
  /*
    // TODO implement this function
    if (skim(2) == 42) {
        impossible();
    } else {
        answer({1, 3});
    }
  */
 
  set<pair<long long, int>> dig;
  // first K elements
  long long s = 0;
  for(int i = 1; i <= K; i++) {
    a[i] = skim(i);
    s += a[i];
    dig.insert({a[i], i});
  }
 
  if(s > 2 * A) {
    impossible();
  }
 
  if(s >= A && s <= 2 * A) {
    vector<int> answ;
    for(int i = 1; i <= K; i++) {
      answ.push_back(i);
    }
    answer(answ);
  }
 
  int ina = K, inb = N, answ = -1;
  while(ina <= inb) {
    int mid = (ina + inb) / 2;
    a[mid] = skim(mid);
 
    if(a[mid] >= A) {
      answ = mid;
      inb = mid - 1;
    } else {
      ina = mid + 1;
    }
  }
 
  if(answ != -1) {
    long long curr = s - a[K] + a[answ];
    if(curr >= A && curr <= 2 * A) {
      vector<int> v;
      for(int i = 1; i < K; i++) {
        v.push_back(i);
      } v.push_back(answ);
      answer(v);
    }
    answ--;
  } else {
    answ = N;
  }
 
  int cnt = 0;
  while(cnt < K && answ > 0) {
    dig.insert({skim(answ), answ});
    cnt++, answ--;
  }
 
  vector<pair<long long, int>> digi;
  for(auto u: dig) {
    digi.push_back(u);
  }
 
  /*
  if(si < A) {
    impossible();
  }
  */
 
  assert(dig.size() <= 20);
 
  int n = digi.size();
  for(int mask = 0; mask < (1 << n); mask++) {
    int ct = __builtin_popcount(mask);
    if(ct != K) continue;
 
    long long sx = 0;
    vector<int> vi;
    for(int i = 0; i < n; i++) {
      if(mask & (1 << i)) {
        sx += digi[i].first;
        sx = min(sx, 2 * A + 2);
        vi.push_back(digi[i].second);
      }
    }
 
    if(sx >= A && sx <= 2 * A) {
      answer(vi);
    }
  }
 
  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