Submission #998281

#	Time	Username	Problem	Language	Result	Execution time	Memory
998281		12345678	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	956 KiB

books

#include <bits/stdc++.h>
#include "books.h"
 
using namespace std;
 
const int nx=1e5+5;
 
long long a[nx];
 
long long query(int idx)
{
    if (!a[idx]) a[idx]=skim(idx);
    return a[idx];
}
 
void solve(int N, int K, long long A, int S) {
    long long sm=0;
    for (int i=1; i<=K; i++) sm+=query(i);
    if (sm>2*A) impossible();
    if (sm>=A)
    {
        vector<int> res;
        for (int i=1; i<=K; i++) res.push_back(i);
        answer(res);
    }
    int l=1, r=N+1;
    while (l<r)
    {
        int md=(l+r)/2;
        if (query(md)>=A) r=md;
        else l=md+1;
    }
    if (l<=N)
    {
        sm=query(l);
        for (int i=1; i<K; i++) sm+=query(i);
        if (sm<=2*A)
        {
            vector<int> res;
            for (int i=1; i<K; i++) res.push_back(i);
            res.push_back(l);
            answer(res);
        }
    }
    N=l-1;
    sm=0;
    for (int i=N-K+1; i<=N; i++) sm+=query(i);
    if (sm<A) impossible();
    if (sm<=2*A)
    {
        vector<int> res;
        for (int i=N-K+1; i<=N; i++) res.push_back(i);
        answer(res);
    }
    for (int i=1; i<K; i++)
    {
        long long sm=0;
        vector<int> res;
        for (int j=1; j<=i; j++) sm+=query(j), res.push_back(j);
        int lft=K-i;
        for (int j=N-lft+1; j<=N; j++) sm+=query(j), res.push_back(j);
        if (A<=sm&&sm<=2*A) answer(res);
    }
}

• 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