| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1115456 | Dan4Life | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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); }
ll ans = sum;
if(ind>=mid+K and ind<=n and a[ind]>=A){
sum=sum-a[mid+K-1]+a[ind];
if(sum>=A and sum<=2*A){ ans[mid+K-1]=ind; answer(ans); exit(0); }
}
return ans;
}
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);
while(l<r){
int mid = (l+r)/2;
if(chk(mid)>2*A) r=mid-1;
else l=mid+1;
}
chk(l); impossible();
}