Submission #729031

#	Time	Username	Problem	Language	Result	Execution time	Memory
729031		NeroZein	A Difficult(y) Choice (BOI21_books)	C++17	80 / 100	1 ms	352 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

const int N = 1000005;

long long a[N]; 
int L[N], R[N];

void solve(int N_, int K_, long long A, int S_) {
    // TODO implement this function
    long long s = 0; 
    int k = K_; 
    int n = N_;
    for (int i = 1; i <= k; ++i) {
      a[i] = skim(i); 
      s += a[i]; 
      L[i] = i;
    }
    L[k + 1] = n + 1; 
    if (s > 2LL * A) {
      impossible(); 
      return; 
    }
    for (int i = k; i >= 0; --i) {
      if (!i) {
        impossible();
        return; 
      }
      R[i] = L[i + 1] - 1;
      a[R[i]] = skim(R[i]); 
      if (s - a[i] + a[R[i]] < A) {
        L[i] = R[i];
      }
      while (L[i] < R[i]) {
        int mid = (L[i] + R[i] + 1) >> 1LL; 
        if (mid != L[i + 1] - 1) {
          a[mid] = skim(mid); 
        } 
        if (s - a[i] + a[mid] > 2LL * A) {
          R[i] = mid - 1;
        } else {
          L[i] = mid;
        }
      }
      s -= a[i];
      s += a[L[i]]; 
      if (s >= A) {
        break; 
      }
    }
    vector<int> v; 
    for (int i = 1; i <= k; ++i) {
      v.push_back(L[i]); 
    }
    answer(v); 
}

• 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: 0 / 20