Submission #811300

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

books

#include <bits/stdc++.h>
#define fs first
#define sc second
#include "books.h"

using namespace std;

void solve(int n, int k, long long a, int s) {
    vector<pair<long long,int> > v;
    long long p=0;
    for(int i=1;i<k;i++){
        v.push_back({skim(i),i});
        p+=v.back().fs;
    }
    int l=k,r=n;
    while(r>l){
        int m=(l+r+1)/2;
        long long z=skim(m)+p;
        if(z>2*a){
            r=m-1;
        }
        else if(a<=z){
            vector<int> ans;
            for(int i=1;i<k;i++){
                ans.push_back(i);
            }
            ans.push_back(m);
            answer(ans);
            return;
        }
        else{
            l=m;
        }
    }
    vector<pair<long long,int> > c;
    long long p2=0;
    c.push_back({skim(l),l});
    p2+=c.back().fs;
    for(int i=l-1;i>l-k;i--){
        c.push_back({skim(i),i});
        p2+=c.back().fs;
    }
    if(p2>=a && 2*a>=p2){
        vector<int> ans;
        for(auto h:c){
            ans.push_back(h.sc);
        }
        answer(ans);
        return;
    }
    reverse(c.begin(),c.end());
    for(int i=0;i<k-1;i++){
        long long z=0;
        for(int j=0;j<i;j++){
            z+=v[j].fs;
        }
        for(int j=i;j<k;j++){
            z+=c[j].sc;
        }
        if(2*a >= z && z>=a){
            vector<int> ans;
            for(int j=0;j<i;j++){
                ans.push_back(v[j].sc);
            }
            for(int j=i;j<k;j++){
                ans.push_back(c[j].sc);
            }
            answer(ans);
            return;
        }
    }
    impossible();
}

• 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