#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
vi memo(1e5,-1);
int n;
int query(int i) {
if (i<0 || i>=n) {
exit(-1);
}
if (memo[i]!=-1) {
return memo[i];
}
memo[i]=skim(i+1);
return memo[i];
}
void solve(int N, int k, ll a, int s) {
n=N;
fill(all(memo),-1);
for (int i=0; i<n; i++) {
query(i);
}
vl vals(k-1);
for (int i=0; i<k-1; i++) {
vals[i]=query(i);
}
int l=k-1,r=n-1;
ll sum=accumulate(all(vals),0ll);
while (l<=r) {
int m=l+(r-l)/2;
ll t=sum+query(m);
if (t<a) {
l=m+1;
}
else if (t>2*a) {
r=m-1;
}
else {
vi inds(k);
iota(all(inds),1);
inds[k-1]=m+1;
answer(inds);
}
}
l=0,r=n-k;
while (l<=r) {
int m=l+(r-l)/2;
ll sum=0;
for (int i=m; i<m+k; i++) {
sum+=query(i);
}
if (sum<a) {
l=m+1;
}
else if (sum>2*a) {
r=m-1;
}
else {
vi inds(k);
iota(all(inds),m+1);
answer(inds);
}
}
impossible();
/*if (n==s) {
vl vals(n);
for (int i=0; i<n; i++) {
vals[i]=skim(i+1);
}
for (int i=0; i<=n-k; i++) {
ll s=accumulate(vals.begin()+i,vals.begin()+i+k,0ll);
if (a<=s && s<=2*a) {
vi inds(k);
iota(all(inds),i+1);
answer(inds);
}
}
for (int i=k; i<n; i++) {
ll s=accumulate(vals.begin(),vals.begin()+k-1,0ll)+vals[i];
if (a<=s && s<=2*a) {
vi inds(k);
iota(all(inds),1);
inds[k-1]=i+1;
answer(inds);
}
}
impossible();
}
else {
int l=0,r=n-k;
while (l<=r) {
int m=l+(r-l)/2;
ll sum=0;
for (int i=m; i<m+k; i++) {
sum+=skim(i+1);
}
if (sum<a) {
l=m+1;
}
else if (sum>2*a) {
r=m-1;
}
else {
vi inds(k);
iota(all(inds),m+1);
answer(inds);
}
}
impossible();
}*/
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |