Submission #797354

#	Time	Username	Problem	Language	Result	Execution time	Memory
797354		tch1cherin	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	336 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.
//
 
map<int, long long> m;
 
long long skim_and_check(int x) {
  if (m.count(x)) {
    return m[x];
  } else {
    return m[x] = skim(x);
  }
}
 
void answer_and_sort(vector<int> v) {
  sort(v.begin(), v.end());
  answer(v);
}
 
void solve(int N, int K, long long A, int S) {
  m = map<int, long long>();
  int l = 0, r = N + 1;
  while (r > l + 1) {
    int mid = (l + r) / 2;
    if (skim_and_check(mid) < A) {
      l = mid; 
    } else {
      r = mid;
    }
  }
  if (l < K) {
    long long sum = 0;
    vector<int> ans;
    for (int i = 1; i <= K; i++) {
      sum += skim_and_check(i);
      ans.push_back(i);
    }
    if (sum >= A && sum <= 2 * A) {
      answer_and_sort(ans); 
    } else {
      impossible();
    }
    return;
  }
  vector<int> ans;
  vector<long long> vals;
  long long sum = 0;
  for (int i = l; i > l - K; i--) {
    vals.push_back(skim_and_check(i));
    ans.push_back(i);
    sum += vals.back();
  }
  if (sum < A) {
    if (r == N + 1) {
      impossible();
      return;
    }
    sum = skim_and_check(r);
    ans = vector<int>();
    ans.push_back(r);
    for (int i = 1; i <= K - 1; i++) {
      ans.push_back(i);
      sum += skim_and_check(i);
    }
    if (sum <= 2 * A) {
      answer_and_sort(ans);
    } else {
      impossible();
    }
  } else {
    if (sum <= 2 * A) {
      answer_and_sort(ans);
      return;
    }
    vector<int> add;
    for (int i = 1; i <= K; i++) {
      sum += skim_and_check(i) - vals.back();
      vals.pop_back();
      ans.pop_back();
      add.push_back(i);
      if (sum <= 2 * A) {
        break;
      }
    }
    if (sum > 2 * A) {
      impossible();
      return;
    }
    vector<int> new_ans;
    for (int v : add) {
      new_ans.push_back(v);
    }
    for (int v : ans) {
      new_ans.push_back(v);
    }
    answer_and_sort(new_ans);
  }
}

• 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