Submission #925105

#	Time	Username	Problem	Language	Result	Execution time	Memory
925105		NintsiChkhaidze	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	700 KiB

books

#include <bits/stdc++.h>
#include "books.h"
typedef long long ll;
#define pb push_back
using namespace std;
long long x[100005],b[100005];
 
void solve(int N, int K, long long A, int S) {    	
    ll s = 0;
    int k = K,n = N;
    
    for (int i = 1; i <= k; i++){
    	x[i] = skim(i);
    	s += x[i];
	}
	if (s > 2*A) impossible();
	
	int l = 1,r = n,id = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (!x[mid]) x[mid] = skim(mid);
		
		if (x[mid] <= A) {
			id = mid;
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	
	s -= x[k];
	if (id + 1 <= n && x[id + 1] + s >= A && x[id + 1] + s <= 2*A){
		vector <int> ans;
		for (int i=1;i<k;i++)
			ans.pb(i);
		ans.pb(id + 1);
		answer(ans);
		return;
	}
		
	int idx = 0;
	for (int i = 1; i <= k; i++)
		b[++idx] = i;
	
	for (int i = id - k + 1; i <= id; i++){
		if (i > k) b[++idx] = i; 
	}
	
	s = 0;
	for (int i = 1; i <= idx; i++){
		if (!x[b[i]]) x[b[i]] = skim(b[i]);
		
		if (i >= k) s -= x[b[i - k]];
		s += x[b[i]];
		if (i < k) continue;
		
		if (s >= A && s <= 2*A){
			vector <int> ans;
			for (int j = i - k + 1; j <= i; j++)
				ans.pb(b[j]);
			answer(ans);
			return;
		}
	}
	
	impossible();
}

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