Submission #859483

#	Time	Username	Problem	Language	Result	Execution time	Memory
859483		maks007	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	53 ms	1412 KiB

books

#include <bits/stdc++.h>
 
#include "books.h"
// #include "grader.cpp"
 
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.
//
 
void solve(int n, int k, long long a, int s) {
    int l = 0, r = n - 1;
    vector <long long> mp(n, -1);
    map <long long, int> rev;
    while(l < r) {
        int mid = (l + r + 1) / 2;
        mp[mid] = skim(mid + 1);
        rev[mp[mid]] = mid;
        if(mp[mid] >= a) r = mid - 1;
        else l = mid; 
    }
    l ++;
    l = min(l, n-1);
    vector <long long> v;
    for(int i = 0; i < k; i ++) {
        if(mp[i] == -1) {
            mp[i] = skim(i+1);
            rev[mp[i]] = i;
        }
        v.push_back(mp[i]);
    }
    for(int i = l; i >= max(0, l-k+1); i --) {
        if(mp[i] == -1) {
            mp[i] = skim(i+1);
            rev[mp[i]] = i;
        }
        v.push_back(mp[i]);
    }
    for(int mask = 0; mask < (1 << (int)v.size()); mask ++) {
        if(__builtin_popcount(mask) != k) continue;
        long long sum = 0;
        vector <int> ans;
        for(int i = 0; i < v.size(); i ++) {
            if(mask & (1 << i)) {
                sum += v[i];
                ans.push_back(rev[v[i]] + 1);
            }
        }
        if(sum >= a && sum <= 2LL * a) {
            answer(ans);
        }
    }
    impossible();
}

Compilation message (stderr)

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

• 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