Submission #1054384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054384		LucaLucaM	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	26 ms	600 KiB

books

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include "books.h"

//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

typedef long long ll;

std::map<int, ll> asked;

ll get(int p) {
  if (asked.count(p)) {
    return asked[p];
  } else {
    return asked[p] = skim(p + 1);
  }
}

void solve(int N, int K, long long A, int S) {
  std::vector<int> indices;
  std::vector<ll> vals;
  for (int i = 0; i < K; i++) {
    indices.push_back(i);
    vals.push_back(get(i));
  }
  int l = 0, r = N - 1, sol = N - 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (get(mid) >= A) {
      r = mid - 1;
      sol = mid;
    } else {
      l = mid + 1;
    }
  }

  for (int i = sol; i >= 0 && i >= sol - K; i--) {
    indices.push_back(i);
    vals.push_back(get(i));
  }

  std::sort(indices.begin(), indices.end());
  std::sort(vals.begin(), vals.end());
  indices.erase(std::unique(indices.begin(), indices.end()), indices.end());
  vals.erase(std::unique(vals.begin(), vals.end()), vals.end());

  int sz = (int) vals.size();
  for (int mask = 0; mask < (1 << sz); mask++) {
    if (__builtin_popcount(mask) != K) {
      continue;
    }
    ll sum = 0;
    for (int i = 0; i < sz; i++) {
      if ((mask >> i) & 1) {
        sum += vals[i];
      }
    }
    if (A <= sum && sum <= 2 * A) {
      std::vector<int> ret;
      for (int i = 0; i < sz; i++) {
        if ((mask >> i) & 1) {
          ret.push_back(indices[i] + 1);
        }
      }
      answer(ret);
      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