Submission #1164811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164811		peacebringer1667	A Difficult(y) Choice (BOI21_books)	C++17	20 / 100	1 ms	428 KiB

books

#include<bits/stdc++.h>
#include "books.h"
#define pir pair <int,int>
#define fi first
#define se second
#define ldb long double
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;

template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}
template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
/*
//g_ : grader
ll g_a[maxn];

ll skim(int i){
	return g_a[i];
}

void answer(vector <int> v){
	cout << "My answer: ";
	for (int x : v) cout << x << " ";
}
void impossible(){
	cout << "My program has deemed it impossible";
}*/
//////////////

ll a[maxn];

int getlwb(int N,ll A){
	int l = 0,r = N - 1,vt = N;
	while (l <= r){
		int w = (l + r)/2;
		
		if (!a[w]) a[w] = skim(w + 1);
		
		if (a[w] >= A){
			vt = w;
			r = w - 1;
		}
		else l = w + 1;
	}
	return vt;
}

void solve(int N,int K,ll A,int S){
	int pivot = getlwb(N,A);
	vector <int> res;
	
	//only one elemenet
	if (pivot != N && a[pivot] <= 2*A && K == 1){
		res.push_back(pivot + 1);
		answer(res);
		return;
	}
	/////////////////
	
	
	//
	ll tsum = a[pivot];
	for (int i = 0 ; i < K - 1 ; i++){
		if (!a[i]) a[i] = skim(i + 1);
		
		tsum += a[i];
		if (tsum > 2*A) break;
		
		if (i == K - 2 && tsum <= 2*A && tsum >= A){
			res.push_back(pivot + 1);
			for (int id = 1 ; id < K ; id++)
			   res.push_back(id);
			sort(res.begin(),res.end());
			
			answer(res);
			return;
		}
	}
	
	//
	int l = 0,r = pivot - K + 1;
	while (l <= r && !res.size()){
		int w = (l + r)/2;
		
		ll tsum = 0;
		for (int i = w ; i < w + K ; i++){
			if (!a[i]) a[i] = skim(i + 1);
			
			tsum += a[i];
			if (tsum > 2*A) break;
		}
		
		if (tsum >= A && tsum <= 2*A){
			for (int id = w ; id < w + K ; id++)
				res.push_back(id + 1);
				
				answer(res);
				return;
		}
		
		if (tsum < A) l = w + 1;
		if (tsum > 2*A) r = w - 1;
	}
	
	sort(res.begin(),res.end());
	
	if (!res.size()) impossible();
	if (res.size()) answer(res);
}

/*
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	g_a[1] = 7;
	g_a[2] = 8; 
	g_a[3] = 9; 
	g_a[4] = 10; 
	g_a[5] = 12; 
	g_a[6] = 15; 
	g_a[7] = 40; 
	g_a[8] = 40; 
	g_a[9] = 40; 
	g_a[10] = 40;
	g_a[11] = 40; 
	g_a[12] = 45; 
	g_a[13] = 50; 
	g_a[14] = 55; 
	g_a[15] = 60;	
	
	
	solve(15,3,20,8);
	

	return 0;
}
*/

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