Submission #1187335

#TimeUsernameProblemLanguageResultExecution timeMemory
1187335kl0989eA Difficult(y) Choice (BOI21_books)C++20
0 / 100
1 ms1192 KiB
#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() vl memo(1e5,-1); ll query(int i) { if (memo[i]!=-1) { return memo[i]; } return memo[i]=skim(i+1); } void solve(int n, int k, ll a, int s) { fill(all(memo),-1); 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); } } impossible(); while (l<=r) { int m=l+(r-l)/2; ll sum=0; for (int i=m; i<m+k; i++) { sum+=query(i); if (i==m && sum*k+k*(k-1)/2>2*a) { sum=2*a+1; break; } } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...