제출 #1115462

#제출 시각아이디문제언어결과실행 시간메모리
1115462Dan4LifeA Difficult(y) Choice (BOI21_books)C++17
20 / 100
4 ms1280 KiB
#include <bits/stdc++.h> #include "books.h" using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) using ll = long long; using vi = vector<int>; const int N = (int)1e5+10; int n, K, ind; ll A, a[N]; vi ans; ll Skim(int i){ if(a[i]!=-1) return a[i]; return a[i]=skim(i); } ll getSum(int mid, int num){ ll s = 0; for(int j = mid; j < mid+num; j++) s+=Skim(j); return s; } int bsearch(ll x){ int l = 1, r = n; while(l<r){ int mid = (l+r)/2; if(Skim(mid)>x) r=mid; else l=mid+1; } return l; } ll chk(int mid){ ll sum = getSum(mid,K); ans.resize(K,0); iota(all(ans),mid); if(sum>=A and sum<=2*A){ answer(ans); exit(0); } return sum; } void solve(int _N, int _K, ll _A, int S) { n = _N; A=_A,K=_K; memset(a,-1,sizeof(a)); ans.resize(K,0); int l = 1, r = n-K+1; ind = bsearch(A); ll sum = getSum(1,K-1); if(ind>=K and ind<=n and sum+a[ind]>=A and sum+a[ind]<=2*A){ iota(all(ans),1); ans[K-1] = ind; answer(ans); exit(0); } while(l<r){ int mid = (l+r)/2; if(chk(mid)>2*A) r=mid-1; else l=mid+1; } chk(l); 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...