Submission #405132

#	Time	Username	Problem	Language	Result	Execution time	Memory
405132		CaroLinda	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	3 ms	328 KiB

books

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

#define sz(x) (int)(x.size())

using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

map<int, long long> mp ;
long long A ;

long long ask(int x) 
{
	if(mp.find(x) != mp.end()) return mp[x] ;
	return mp[x] = skim(x) ;
}

bool check(long long s) { return  s >= A && s <= A+A ;}

void solve(int N, int K, long long a, int S) 
{
	A = a ;

	int l = 1, r = N , mid , best = -1 ;

	while( l <= r )
	{
		mid = (l+r)>>1 ;

		if( ask(mid) <= A ) { best = mid ; l = mid+1 ; }
		else r = mid-1 ;

	}

	if( best == -1 ) impossible() ;

	vector<long long> v ;
	vector<int> R ;

	if( best <= 2*K ) 
	{ 
		for(int i = 1 ; i <= best; i++ ) 
		{
			v.push_back(ask(i)) ;
			R.push_back(i) ;
		} 
	}
	else 
	{
		for(int i = 1 ; i <= K ; i++ ) v.push_back(ask(i)) , R.push_back(i) ;
		for(int i = best-K+1 ; i <= best ; i++ ) v.push_back(ask(i)) , R.push_back(i) ;
	}

	if(best+1 <= N && best >= K-1)
	{
		long long s = ask(best+1) ;
		for(int i = 0 ; i < K-1 ; i++ ) s += v[i] ;

		if( check(s) )
		{
			vector<int> ans = {best+1} ;
			for(int i = 1 ; i < K ; i++ ) ans.push_back(i) ;
			answer(ans) ;
			return ;
		}

	}

	if( best < K ) impossible() ;

	long long s = 0 ;
	for(int i = 0 ; i < K ; i++ ) s += v[i] ;

	if( check(s) ) 
	{
		vector<int> ans ;
		for(int i = 0 ; i < K ; i++ ) ans.push_back(R[i]) ;
		answer(ans) ;
		return ;
	}

	for(int i = K ; i < sz(v) ; i++ )
	{
		s -= v[i-K] ;
		s += v[i] ;

		if(check(s)) 
		{
			vector<int> ans ;
			for(int j = i-K+1 ; j <= i ; j++ ) ans.push_back(R[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