Submission #817430

#	Time	Username	Problem	Language	Result	Execution time	Memory
817430		MohamedAhmed04	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	1124 KiB

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

const int MAX = 1e5 + 10 ;

long long arr[MAX] ;

long long query(int idx)
{
	if(arr[idx] == -1)
		arr[idx] = skim(idx) ;
	return arr[idx] ;
}

void solve(int n, int k, long long a, int s) 
{
	memset(arr , -1 , sizeof(arr)) ;
	long long sum = 0 ;
	for(int i = 1 ; i <= k-1 ; ++i)
		arr[i] = skim(i) , sum += arr[i] ;
	int l = k , r = n ;
	int idx = l ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(sum + query(mid) <= 2 * a)
			idx = mid , l = mid+1 ;
		else
			r = mid-1 ;
	}
	query(idx) ;
	sum += arr[idx] ;
	if(sum > 2*a)
	{
		impossible() ;
		return ;
	}
	else if(sum >= a)
	{
		vector<int>ans ;
		for(int i = 1 ; i <= k-1 ; ++i)
			ans.push_back(i) ;
		ans.push_back(idx) ;
		answer(ans) ;
		return ;
	}
	int cur = k-1 ;
	for(int i = idx-1 ; i >= 1 && cur > 0 ; --i)
	{
		sum += query(i) ;
		sum -= query(cur) , --cur ;
		assert(sum <= 2*a) ;
		if(sum >= a)
		{
			vector<int>ans ;
			for(int j = 1 ; j <= cur ; ++j)
				ans.push_back(j) ;
			for(int j = i ; j <= idx ; ++j)
				ans.push_back(j) ;
			answer(ans) ;
			return ;
		}
	}
	impossible() ;
	return ;
}

• 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