Submission #434951

#	Time	Username	Problem	Language	Result	Execution time	Memory
434951		dqhungdl	A Difficult(y) Choice (BOI21_books)	C++17	45 / 100	22 ms	328 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

long long cache[100005];

long long skimming(int id) {
	if(cache[id]!=0)
		return cache[id];
	return cache[id]=skim(id);
}

void solve(int N, int K, long long A, int S) {
	int l=K,r=N,pivot=K;
	while(l<=r) {
		int mid=(l+r)/2;
		if(skimming(mid)*K<=2*A) {
			pivot=mid;
			l=mid+1;
		} else
			r=mid-1;
	}
	vector<pair<long long,int>> V;
	for(int i=max(1,pivot-9);i<=min(pivot+10,N);i++)
		V.push_back({skimming(i),i});
	for(int mask=0;mask<(1<<V.size());mask++) {
		if(__builtin_popcount(mask)!=K)
			continue;
		long long sum=0;
		for(int i=0;i<V.size();i++)
			if((mask>>i)&1)
				sum+=V[i].first;
		if(A<=sum&&sum<=2*A) {
			vector<int> rs;
			for(int i=0;i<V.size();i++)
				if((mask>>i)&1)
					rs.push_back(V[i].second);
			answer(rs);
		}
	}
	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i=0;i<V.size();i++)
      |               ~^~~~~~~~~
books.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int i=0;i<V.size();i++)
      |                ~^~~~~~~~~

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