Submission #558926

#	Time	Username	Problem	Language	Result	Execution time	Memory
558926		benson1029	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	28 ms	336 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

vector< pair<long long,int> > v;
vector<int> ans;

void solve(int N, int K, long long A, int S) {
    if(N>=25) {
        int l = 1, r = N, mid;
        while(l<=r) {
            mid = (l+r)/2;
            if(skim(mid) <= A) l = mid+1;
            else r = mid-1;
        }
        for(int i=1; i<=min(K, l); i++) {
            v.push_back({skim(i), i});
        }
        for(int i=max(K+1, l-K); i <= min(l, N); i++) {
            v.push_back({skim(i), i});
        }
    } else {
        for(int i=1; i<=N; i++) {
            v.push_back({skim(i), i});
        }
    }
    for(int i=0; i<(1<<v.size()); i++) {
        if(__builtin_popcount(i) != K) continue;
        long long sum = 0;
        for(int j=0; j<v.size(); j++) {
            if((i>>j)%2) sum += v[j].first;
        }
        if(sum >= A && sum <= 2*A) {
            for(int j=0; j<v.size(); j++) {
                if((i>>j)%2) ans.push_back(v[j].second);
            }
            answer(ans);
            return;
        }
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:32:23: 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 j=0; j<v.size(); j++) {
      |                      ~^~~~~~~~~
books.cpp:36:27: 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]
   36 |             for(int j=0; j<v.size(); j++) {
      |                          ~^~~~~~~~~

• 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