제출 #1150704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150704		Ludissey	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	19 ms	416 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

map<int,int> mp;
int ski(int x){
    if(mp.find(x)!=mp.end()) return mp[x];
    return mp[x]=skim((int)(x+1));
}


void solve(signed N, signed K, long long A, signed S) {
    vector<pair<int,int>> a;
    set<int> st;
    for (int i = 0; i < K; i++) {
        a.push_back({ski(i),i});
        st.insert(i);
    }
    int l=K, r=N-1;
    while(l<r){
        int mid=(l+r)/2;
        int v=ski(mid);
        if(v>=A) {
            r=mid;
        }else{
            l=mid+1;
        }
    }
    int mxI=r;
    for (int i = mxI; i >= max(0LL, (mxI-K)); i--)
    {
        if(st.find(i)!=st.end()) continue;
        a.push_back({ski(i),i});
    }
    sort(all(a));
    vector<int> mask(K, 1);
    mask.resize(sz(a), 0);
    vector<signed> ans;
    do {
        int sum=0;
        for (int i = 0; i < sz(a); i++) {
            if (mask[i]) sum+=a[i].first;
        }
        if(sum>=A&&sum<=2*A){
            for (int i = 0; i < sz(a); i++) {
                 if (mask[i]) ans.push_back(a[i].second+1);
            }
            answer(ans);
            return;
        }
    } while (prev_permutation(mask.begin(), mask.end()));
    impossible();
    return;
}

• 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