Submission #1111930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111930		fryingduc	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	592 KiB

books

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#include "books.h"
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, k, q;
long long m;
long long a[maxn];
long long ans[maxn];

int cnt_asks;

long long ask(int id) {
  if(a[id]) return a[id];
  
  ++cnt_asks;
  if(cnt_asks > q) {
    assert(0);
    exit(0);
  }
  #ifdef duc_debug
    return a[id] = ans[id];
  #else
    return a[id] = skim(id);
  #endif
}
void solve(int N, int K, long long A, int S) {
  n = N, k = K, m = A, q = S;
  long long sum = 0;
  for(int i = 1; i <= k; ++i) {
    sum += ask(i);
  }
  if(sum > 2 * m) {
    impossible();
    return;
  }
  sum -= a[k];
  int l = k, r = n;
  int res = -1;
  while(l <= r) {
    int mid = (l + r) >> 1;
    if(sum + ask(mid) >= m) {
      res = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  if(res != -1) {
    if(a[res] + sum <= 2 * m) {
      vector<int> ds;
      for(int i = 1; i < k; ++i) ds.push_back(i);
      ds.push_back(res);
      
      answer(ds);
      return;
    }
  } else {
    res = n + 1;
  }
  sum += a[--res];
  set<int> s;
  for(int i = 1; i < k; ++i) s.insert(i);
  s.insert(res);
  for(int i = res - 1, j = k - 1; i > 0 and j > 0; --i, --j) {
    if(sum >= m) break;
    sum -= ask(j);
    s.erase(j);
    s.insert(i);
    sum += ask(i);
  }
  if(sum < m || sum > m * 2) {
    impossible();
    return;
  }
  vector<int> ds;
  for(auto i:s) ds.push_back(i);
  answer(ds);
}

• 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