Submission #530070

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

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
typedef long long ll;
const int mxN=100010;
//
// --- 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.
//
ll N, K, lim;
ll A[mxN];
int cursor;
bool f1()
{
    A[N]=skim(N);
    for(int i=1;i<=K;i++)   A[i]=skim(i);
    if(A[N]<lim)
    {
        cursor=N+1;
        return false;
    }
    int s=1, e=N;
    while(s!=e)
    {
        int mid=(s+e)/2;
        if(skim(mid)>=lim) e=mid;
        else    s=mid+1;
    }
    cursor=e;
    A[cursor]=skim(cursor);
    if(cursor<K)    return false;
    ll sum=0;
    for(int i=1;i<K;i++)    sum+=A[i];
    sum+=A[cursor];
    if(sum<=2*lim)
    {
        vector <int> v;
        for(int i=1;i<K;i++)    v.push_back(i);
        v.push_back(cursor);
        answer(v);
        return true;
    }
    return false;
}
bool f2()
{
    if(cursor<=K)    return false;
    ll sum=0;
    for(int i=1;i<=K;i++)   sum+=A[i];
    if(sum>2*lim)   return false;
    if(sum>=lim)
    {
        vector <int> v;
        for(int i=1;i<=K;i++)   v.push_back(i);
        answer(v);
        return true;
    }
    for(int i=cursor-K;i<=cursor-1;i++) A[i]=skim(i);
    for(int i=K;i>=1;i--)
    {
        sum-=A[i];
        sum+=A[cursor-K-1+i];
        if(sum>=lim)
        {
            vector <int> v;
            for(int j=1;j<i;j++)    v.push_back(j);
            for(int j=i;j<=K;j++)   v.push_back(cursor-K-1+j);
            answer(v);
            return true;
        }
    }
    return false;
}
void solve(int n, int k, long long a, int S) {
    // TODO implement this function
    N=n, K=k, lim=a;
    bool ok=f1();
    if(!ok) ok=f2();
    if(!ok) 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