Submission #1115429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115429		Dan4Life	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	6 ms	1360 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;
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();
}

• 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