Submission #1265058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265058		lopkus	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	47 ms	1600 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
//
// --- 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.
//

void solve(int n, int k, long long a, int s) {
    // TODO implement this function
    /**
    if (skim(2) == 42) {
        impossible();
    } else {
        answer({1, 3});
    }**/
  std::vector<std::pair<int, int>> intervals;
  for(int i = 1; i + k - 1 <= n; i++) {
    intervals.push_back({i, i + k - 1});
  }
  std::map<int, long long> was, asked;
  std::function<long long(int)> ask = [&](int i) {
    if(was[i]) {
      return asked[i];
    }
    was[i] = 1;
    long long t = skim(i);
    asked[i] = t;
    return t;
  };
  std::vector<std::pair<long long, int>> v;
  std::vector<int> q(n + 1);
  for(int i = 1; i <= k; i++) {
    v.push_back({ask(i), i});
    q[i] = 1;
  }
  int l = k, r = n, ans = n;
  while(l <= r) {
    int mid = (l + r) / 2;
    if(ask(mid) >= a) {
      r = mid - 1;
      ans = mid;
    }
    else {
      l = mid + 1;
    }
  }
  for(int i = ans; i >= std::max(k + 1, ans - k - 1); i--) {
    v.push_back({ask(i), i});
  }
  ans = - 1;
  for(int mask = 0; mask < (1LL << (v.size())); mask++) {
    if(__builtin_popcount(mask) != k) {
      continue;
    }
    long long sum = 0;
    for(int i = 0; i < v.size(); i++) {
      if(mask & (1LL << i)) {
        sum += v[i].first;
      }
    }
    if(sum >= a && sum <= 2LL * a) {
      ans = mask;
      break;
    }
  }
  if(ans == - 1) {
    impossible();
  }
  else {
    std::vector<int> w;
    for(int i = 0; i < v.size(); i++) {
      if(ans & (1LL << i)) {
        w.push_back(v[i].second);
      }
    }
    answer(w);
  }
}

• 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