Submission #655259

#	Time	Username	Problem	Language	Result	Execution time	Memory
655259		600Mihnea	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	4 ms	1124 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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.
//

typedef long long ll;

void solve(int n, int k, ll a, int skims) {
        // TODO implement this function
        vector<ll> v(n+1),v2;
        set<int> s;
        for (int i=1;i<=k;i++){
                v[i]=skim(i);
                s.insert(i);
        }

        int low=1,high=n,cnt_under=0;
        v[n]=skim(n);
        while (low<=high){
                int mid=(low+high)/2;
                if(skim(mid)<=a){
                        cnt_under=mid;
                        low=mid+1;
                }else{
                        high=mid-1;
                }
        }
        for (int i=cnt_under-k;i<=cnt_under+1;i++){
                if(1<=i&&i<=n){
                        v[i]=skim(i);
                        s.insert(i);
                }
        }
        vector<int> inds;
        for (auto &i : s){
                inds.push_back(i);
                v2.push_back(v[i]);
        }

        /// secventa, prefix

        for (int r=k-1;r<(int)inds.size();r++){
                for (int c=1;c<=k;c++){
                        ll sum=0;
                        for (int i=r-c+1;i<=r;i++){
                                sum+=v2[i];
                        }
                        for(int i=0;i<k-c;i++){
                                sum+=v2[i];
                        }
                        if(a<=sum&&sum<=2*a){
                                vector<int> sol;
                                for (int i=r-c+1;i<=r;i++){
                                        sol.push_back(inds[i]);
                                }
                                for(int i=0;i<k-c;i++){
                                        sol.push_back(inds[i]);
                                }
                                assert((int)sol.size()==k);
                                answer(sol);
                                return;
                        }

                }
        }

        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