Submission #729207

#	Time	Username	Problem	Language	Result	Execution time	Memory
729207		NeroZein	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;
 
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;
      if (!a[R[i]]) {
				a[R[i]] = skim(R[i]); 				
			}
      if (s - a[i] + a[R[i]] <= 2LL * A) {
        L[i] = R[i];
      }
      while (L[i] < R[i]) {
        int mid = (L[i] + R[i] + 1) >> 1LL; 
        if (!a[mid]) {
          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: 20 / 20