제출 #1115471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115471		Dan4Life	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	2 ms	1104 KiB

books

#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){
	if(num<=0) return 0;
	ll s = 0;
	for(int j = mid; j < mid+num; j++) s+=Skim(j);
	return s;
}

int bsearch(int st, ll x){
	int l = st, r = n+1;
	while(l<r){
		int mid = (l+r)/2;
		if(Skim(mid)>x) r=mid;
		else l=mid+1;
	}
	return l;
}

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 ind = bsearch(K, A);
	ll sum = getSum(1,K-1);
	if(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);
	}
	sum = getSum(1,K);
	if(sum>=A and sum<=2*A){ iota(all(ans),1); answer(ans); exit(0); 	}
	deque<int> ans2(K,0); iota(all(ans2),1);
	int j = max(K+1,ind-K)-1;
	for(int i = 1; i <= K; i++){
		sum-=a[i]; ans2.pop_front();
		if(j+i>=ind) break; 
		sum+=a[j+i]; ans2.push_back(j+i);
		if(sum>=A and sum<=2*A){
			ans.clear();
			for(auto u : ans2) ans.pb(u);
			answer(ans); exit(0);
		}
	}
	impossible();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20