Submission #598713

#	Time	Username	Problem	Language	Result	Execution time	Memory
598713		slime	A Difficult(y) Choice (BOI21_books)	C++14	45 / 100	1 ms	1064 KiB

books

#include "books.h"
#include "bits/stdc++.h"
using namespace std;
void solve(int N, int K, long long A, int S) {
  long long x[N+1];
  for(int i=1; i<=K; i++) x[i] = skim(i);
  for(int i=max(K+1, N-K+1); i<=N; i++) x[i] = skim(i);
  long long sfront = 0, sback = 0;
  for(int i=1; i<=K; i++) sfront += x[i];
  for(int i=N-K+1; i<=N; i++) sback += x[i];
  if(sfront > 2 * A) {
    impossible(); return;
  }
  if(sback < A) {
    impossible(); return;
  }
  for(int i=1; i<K; i++) {
    long long smid = 0;
    for(int j=1; j<=i; j++) smid += x[j];
    for(int j=N-(K-i)+1; j<=N; j++) smid += x[j];
    if(smid >= A && smid <= 2 * A) {
      vector<int> v;
      for(int j=1; j<=i; j++) v.push_back(j);
      for(int j=N-(K-i)+1; j<=N; j++) v.push_back(j);
      answer(v);
      return;
    }
  }
  if(A <= sfront && sfront <= 2 * A) {
    vector<int> v;
    for(int i=1; i<=K; i++) v.push_back(i);
    answer(v);
    return;
  }
  if(A <= sback && sback <= 2 * A) {
    vector<int> v;
    for(int i=N-K+1; i<=N; i++) v.push_back(i);
    answer(v);
    return;
  }
  for(int i=K; i>=1; i--) {
    long long fsum = 0, ssum = 0;
    for(int j=1; j<i; j++) {
      ssum += x[j];
    }
    long long e = 0;
    fsum = ssum + x[i];
    for(int j=N-(K-i)+1; j<=N; j++) {
      e += x[j];
    }
    fsum += e;
    ssum += e + x[N - (K-i)];
    if(fsum < A && 2 * A < ssum) {
      int lb = i, rb = N - (K-i);
      long long pref = 0, suf = 0;
      for(int j=1; j<i; j++) pref += x[j];
      for(int j=N-(K-i)+1; j<=N; j++) suf += x[j];
      while(lb < rb) {
        int mid = (lb + rb) >> 1;
        long long val = skim(mid);
        if(val + pref + suf >= A) {
          rb = mid;
        }
        else {
          lb = mid + 1;
        }
      }
      long long sk = skim(lb);
      if(sk + pref + suf >= A && sk + pref + suf <= 2 * A) {
        vector<int> v;
        for(int j=1; j<i; j++) v.push_back(j);
        for(int j=N-(K-i)+1; j<=N; j++) v.push_back(j);
        v.push_back(lb);
        answer(v);
      }
      else {
        impossible();
      }
      return;
    }
  }
  impossible();
}

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