Submission #857551

#	Time	Username	Problem	Language	Result	Execution time	Memory
857551		iskhakkutbilim	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	72 ms	1444 KiB

books

#include <bits/stdc++.h>
#include "books.h"
 
 
using namespace std;
 
void solve(int N, int K, long long A, int S){
	vector<long long> a(N + 2, -1);
	set<int> st;
	for(int i = 1;i <= K; i++){
		a[i] = skim(i);
		st.insert(i);
	}
	int l = 0, r = N+1;
	while(l + 1 < r){
		int mid = (l + r)>>1;
		if(a[mid] == -1) a[mid] = skim(mid);	
		if(a[mid] >= A) r = mid;
		else l = mid;
	}
	if(r > N) r--;
	for(int i = r; i >= 1 && st.size() <= 2*K; i--){
		if(a[i] == -1) a[i] = skim(i);
		st.insert(i);
	}
	vector<int> all;
	for(int x : st) all.push_back(x);	
	for(int mask = 1; mask < (1<<(int)all.size()); mask++){
		if(__builtin_popcount(mask) != K) continue;
		long long sum = 0;
		vector<int> v;
		for(int i = 0;i < all.size(); i++){
			if(mask & (1LL<<i)){
				sum+= a[all[i]];
				v.push_back(all[i]);
			}
		}
		if(sum >= A && sum <= 2*A && v.size() == K){
			answer(v);
		}
	}
	impossible();
}
/*
8 4 25 15
3 8 11 15 25 26 30 42
*/

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:22:37: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |  for(int i = r; i >= 1 && st.size() <= 2*K; i--){
      |                           ~~~~~~~~~~^~~~~~
books.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i = 0;i < all.size(); i++){
      |                 ~~^~~~~~~~~~~~
books.cpp:38:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   if(sum >= A && sum <= 2*A && v.size() == K){
      |                                ~~~~~~~~~^~~~

• 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