Submission #1137138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137138		Alihan_8	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	28 ms	1192 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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.
//

using i64 = long long;

void solve(int n, int k, long long A, int S) {
	vector <i64> a(n + 1, -1);
	
	auto qry = [&](int x){
		return a[x] != -1 ? a[x] : a[x] = skim(x);
	};
	
	int l = 0, r = n + 1;
	
	while ( l + 1 < r ){
		int m = (l + r) / 2;
		
		if ( qry(m) <= A ) l = m;
		else r = m;
	}
	
	i64 mn = 0;
	
	for ( int i = 1; i <= k; i++ ) mn += qry(i);
	
	if ( l >= k ){
		i64 mx = 0;
		
		for ( int i = l; i > l - k; i-- ) mx += qry(i);
		
		if ( mn <= A * 2 && mx >= A ){
			vector <int> p;
			
			for ( int i = 1; i <= l; i++ ){
				if ( i <= k || i > l - k ) p.push_back(i);
			}
			
			int m = p.size();
			
			for ( int mask = 0; mask < (1 << m); mask++ ){
				if ( __builtin_popcount(mask) != k ) continue;
				
				i64 sum = 0;
				
				vector <int> idx;
				
				for ( int i = 0; i < m; i++ ){
					if ( mask >> i & 1 ){
						idx.push_back(p[i]);
						sum += qry(p[i]);
					}
				}
				
				if ( sum >= A && sum <= A * 2 ) answer(idx);
			}
		}
	}
	
	if ( r <= n ){
		i64 v = mn - qry(k) + qry(r);
		
		if ( v <= A * 2 ){
			vector <int> idx;
			
			for ( int i = 1; i < k; i++ ) idx.push_back(i);
			
			idx.push_back(r);
			
			answer(idx);
		}
	}
	
	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