Submission #894255

#	Time	Username	Problem	Language	Result	Execution time	Memory
894255		box	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1376 KiB

books

#include "bits/stdc++.h"
using namespace std;
 
#include "books.h"
 
void solve(int n, int k, long long A, int s) {
  vector<long long> a(n, -1);
 
  auto qry = [&](int i) {
    if (~a[i]) return a[i];
    return a[i] = skim(i + 1);
  };
  int low = k, hi = n;
  while (low < hi) {
    int mid = (low + hi) / 2;
    if (qry(mid) >= A)
      hi = mid;
    else
      low = mid + 1;
  }
  if (low < n) {
    __int128 sum = qry(low);
    for (int i = 0; i < k - 1; i++) sum += qry(i);
    if (sum >= A && sum <= A * 2) {
      vector<int> inds(k);
      iota(inds.begin(), inds.end(), 1);
      inds.back() = low + 1;
      answer(inds);
      return;
    }
  }
  vector<int> pos;
  low--;
  for (int i = 0; i < k; i++) {
    pos.push_back(i);
    if (low - i >= 0) pos.push_back(low - i);
  }
  sort(pos.begin(), pos.end());
  pos.erase(unique(pos.begin(), pos.end()), pos.end());
  for (int i = 0; i < (int)pos.size() - k + 1; i++) {
    __int128 sum = 0;
    for (int j = i; j < i + k; j++) sum += qry(pos[j]);
    if (sum >= A && sum <= A * 2) {
      vector<int> inds(k);
      for (int u = 0; u < k; u++) inds[u] = pos[i + u] + 1;
      answer(inds);
      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