제출 #1115429

#제출 시각아이디문제언어결과실행 시간메모리
1115429Dan4LifeA Difficult(y) Choice (BOI21_books)C++17
0 / 100
6 ms1360 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; ll a[N]; ll Skim(int i){ if(a[i]!=-1) return a[i]; return a[i]=skim(i); } ll sum(int mid, int num){ ll s = 0; for(int j = mid; j < mid+num; j++) s+=Skim(j); return s; } void solve(int _N, int K, ll A, int S) { n = _N; memset(a,-1,sizeof(a)); int l = 1, r = n-K+1; while(l<r){ int mid = (l+r)/2; ll xd = sum(mid,K); vi ans(K,0); iota(all(ans),mid); if(xd>=A and xd<=2*A){ answer(ans); return; } int l2 = mid+K, r2 = n; while(l2<r2){ int mid2 = (l2+r2+1)/2; ll nsum = xd+Skim(mid2); if(nsum>=A and nsum<=2*A){ ans[K-1] = mid2; answer(ans); return; } if(nsum>2*A) r2=mid2-1; else l2=mid2; } if(xd>2*A) r=mid-1; else l=mid+1; } ll xd = sum(l,K); vi ans(K,0); iota(all(ans),l); if(xd>=A and xd<=2*A){ answer(ans); return; } xd-=a[l+K-1]; int l2 = l+K, r2 = n; while(l2<r2){ int mid2 = (l2+r2+1)/2; ll nsum = xd+Skim(mid2); if(nsum>=A and nsum<=2*A){ ans[K-1] = mid2; answer(ans); return; } if(nsum>2*A) r2=mid2-1; else l2=mid2; } 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...