Submission #403379

#	Time	Username	Problem	Language	Result	Execution time	Memory
403379		Nordway	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	2 ms	400 KiB

books

#include <bits/stdc++.h>
#include <books.h>
 
#define sz(v) (int)v.size()
#define pb push_back
 
using namespace std;
 
 
typedef long long ll;
 
const int N = 1e5 + 1;
 
bool asked[N];
 
ll x[N];
 
ll ask (int i) {
  	if (!i) return 0ll;
	if (asked[i]) return x[i];
	asked[i] = true;
	x[i] = skim(i);
	return x[i];
}
 
void solve(int n,int k,ll A,int s){
	for (int i = 1; i <= n; i++) {
		asked[i] = false;
	}
 
	int l = 1, r = n, R = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ask(mid) > A + A) r = mid - 1;
		else R = mid, l = mid + 1;
	}
	l = 1, r = R;
	int L = 0;
  	if (ask(R) <= A) {
      if (L < k) impossible();
      ll sum = 0;
      for (int i = 1; i <= k; i++) {
        sum += ask(i);
        if (sum > A + A) impossible();
      }
      if (sum >= A) {
        vector <int> ans;
        for (int i = 1; i <= k; i++) {
          ans.pb(i);
        }
        answer(ans);
      }
      else {
        int j = max(L - k + 1, k + 1);
        vector <int> ans;
        for (int i = 1; i <= k; i++) {
          	ans.pb(i);
        }
        for (int i = 1; i <= k; i++) {
         	if (j > L) break;
          	sum -= ask(i);
          	sum += ask(j);
          	ans[i - 1] = j;
          	j++;
            if (sum >= A) break;
        }
        if(sum >= A){
          answer(ans);
        }
        else {
          impossible();
        }
      }
    }
  	else {
      while (l <= r) {
          int mid = (l + r) / 2;
          if (ask(mid) > A) r = mid - 1;
          else L = mid, l = mid + 1;
      }
      if (L < k - 1) {
        impossible();
      }
      ll sum = 0;
      vector <int> ans;
      for (int i = 1; i <= min(L, k); i++) {
        sum += ask(i);
        ans.pb(i);
        if (sum > A + A) impossible();
      }
      if (sum >= A) {
        if (sz(ans) < k) impossible();
        else answer(ans);
      }
      else {
        if (sz(ans) < k) {
          sum += ask(L + 1);
          ans.pb(L + 1);
          if (sum >= A && sum <= A + A) answer(ans);
          else impossible();
        }
        else {
          ans.pop_back();
          sum -= ask(k);
          sum += ask(L + 1);
          ans.pb(L + 1);
          if (sum >= A && sum <= A + A) answer(ans);
          else impossible();
        }
      }
      
	}
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:20:13: warning: array subscript -1 is below array bounds of 'bool [100001]' [-Warray-bounds]
   20 |  if (asked[i]) return x[i];
      |      ~~~~~~~^
books.cpp:14:6: note: while referencing 'asked'
   14 | bool asked[N];
      |      ^~~~~
books.cpp:21:9: warning: array subscript -1 is below array bounds of 'bool [100001]' [-Warray-bounds]
   21 |  asked[i] = true;
      |  ~~~~~~~^
books.cpp:14:6: note: while referencing 'asked'
   14 | bool asked[N];
      |      ^~~~~
books.cpp:22:5: warning: array subscript -1 is below array bounds of 'll [100001]' {aka 'long long int [100001]'} [-Warray-bounds]
   22 |  x[i] = skim(i);
      |  ~~~^
books.cpp:16:4: note: while referencing 'x'
   16 | ll x[N];
      |    ^
books.cpp:20:26: warning: array subscript -1 is below array bounds of 'll [100001]' {aka 'long long int [100001]'} [-Warray-bounds]
   20 |  if (asked[i]) return x[i];
      |                       ~~~^
books.cpp:16:4: note: while referencing 'x'
   16 | ll x[N];
      |    ^

• 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