제출 #1265026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265026		lopkus	A Difficult(y) Choice (BOI21_books)	C++20	10 / 100	2 ms	2376 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});
  }
  int l = 0, r = intervals.size() - 1, ans = - 1;
  std::vector<int> was(n + 1);
  std::vector<long long> asked(n + 1);
  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;
  };
  while(l <= r) {
    int mid = (l + r) / 2;
    long long sum = 0;
    for(int i = intervals[mid].first; i <= intervals[mid].second; i++) {
      sum += ask(i);
    }
    if(sum >= a && sum <= 2LL * a) {
      ans = mid;
      break;
    }
    if(sum > 2LL * a) {
      r = mid - 1;
    }
    else {
      l = mid + 1;
    }
  }
  if(ans == - 1) {
    impossible();
  }
  else {
    std::vector<int> w;
    for(int i = intervals[ans].first; i <= intervals[ans].second; i++) {
      w.push_back(i);
    }
    answer(w);
  }
}

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