Submission #513865

#	Time	Username	Problem	Language	Result	Execution time	Memory
513865		lorenzoferrari	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	1 ms	272 KiB

books

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

/*
osservazioni banali:
* se k*(k+1)/2 > a, impossible
* altri pruning banali

what would be my strategy if I knew the whole array x?


if x[i+1] - x[i] <= a and I'm under [a,2a] and increase an index by one, I will
never be over

approach: start with [1, ..., k]
for (int i = k; i > 1; --i):
  binsearch the maximum position you can place yourself
  -> it works if x[i+1]-x[i] <= a
  -> does it always work?
    is it possible to chosoe something "too big"
*/

LL skim(int i); // 1 <= i <= N
void answer(vector<int> v);
void impossible();

map<int, int> books;

LL ask(int i) {
  if (books.find(i) == books.end())
    books[i] = skim(i);
  return books[i];
}

void solve(int n, int k, LL a, int s) {
  assert(s);
  vector<int> v(k);
  LL sum = 0;
  for (int i = 0; i < k; ++i) {
    v[i] = i+1;
    sum += ask(v[i]);
  }
  if (sum > 2 * a) impossible();
  if (a <= sum && sum <= 2 * a) answer(v);
  for (int i = k - 1; i > 0; --i) {
    int r = (i == k - 1 ? n+1 : v[i + 1]);
    int l = i + 1;
    while (r - l > 1) {
      int m = (r + l) / 2;
      int newsum = sum - ask(v[i]) + ask(m);
      if (a <= newsum && newsum <= 2 * a) {
        v[i] = m;
        answer(v);
      }
      if (newsum < a) {
        l = m;
      } else {
        r = m;
      }
    }
    sum += ask(l) - ask(v[i]);
    v[i] = l;
    if (a <= sum && sum <= 2 * a) answer(v);
  }
  impossible();
}

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