Submission #1187328

#TimeUsernameProblemLanguageResultExecution timeMemory
1187328kl0989eA Difficult(y) Choice (BOI21_books)C++20
20 / 100
2 ms2732 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); } } vl mx(n),mn(n); for (int i=0; i<n; i++) { if (memo[i]!=-1) { mn[i]=memo[i]; } else { mn[i]=max(mn[i-1],1ll); } } for (int i=n-1; i>=0; i--) { if (memo[i]!=-1) { mx[i]=memo[i]; } else if (i!=n-1) { mx[i]=min((ll)1e17,mx[i+1]-1); } else { mx[i]=1e17; } } l=0,r=n-k; while (accumulate(mn.begin()+r,mn.begin()+r+k,0ll)>2*a) { r--; } while (accumulate(mx.begin()+l,mx.begin()+l+k,0ll)<a) { l++; } 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...