제출 #1265054

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

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