Submission #985964

#	Time	Username	Problem	Language	Result	Execution time	Memory
985964		AlphaMale06	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	42 ms	1620 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

using ll = long long;

//void impossible();
//long long skim(int pos);
//void answer(vector<int> v);

void solve(int n, int k, ll A, int s) {
    ll a[n+1];
    ll sum=0;
    vector<int> opened;
    for(int i=1; i<=k; i++){
        a[i]=skim(i);
        sum+=a[i];
        opened.push_back(i);
    }
    if(sum>=A && sum<=2*A){
        vector<int> ans;
        for(int i=1; i<=k; i++)ans.push_back(i);
        answer(ans);
        return;
    }
    else if(k==n || sum>2*A){
        impossible();
        return;
    }
    sum-=a[k];
    int l=k+1, r=n;
    while(l<=r){
        int s = l+r>>1;
        a[s]=skim(s);
        if(sum+a[s]<=2*A)l=s+1;
        else r=s-1;
    }
    for(int i=r; i>=max(k+1, r-k+1); i--){
        a[i]=skim(i);
        opened.push_back(i);
    }
    sort(opened.begin(), opened.end());
    n=opened.size();
    int mask = 1<<n;
    for(int i=1; i< mask; i++){
        if(__builtin_popcount(i)!=k)continue;
        vector<int> ans;
        ll nsum=0;
        for(int j=0; j<n; j++){
            if(i & (1<<j)){
                ans.push_back(opened[j]);
                nsum+=a[opened[j]];
            }
        }
        if(nsum>=A && nsum<=2*A){
            answer(ans);
            return;
        }
    }
    impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int s = l+r>>1;
      |                 ~^~

• 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