제출 #782935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782935		Hanksburger	A Difficult(y) Choice (BOI21_books)	C++17	60 / 100	2 ms	428 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long x[100005];
vector<int> ans;
void solve(int n, int k, long long a, int s)
{
    long long l=1, r=n-k+1;
    while (l<=r)
    {
        long long mid=(l+r)/2, sum=0;
        for (long long i=mid; i<mid+k; i++)
        {
            if (!x[i])
                x[i]=skim(i);
            sum+=x[i];
        }
        if (a<=sum && sum<=a*2)
        {
            for (long long i=mid; i<mid+k; i++)
                ans.push_back(i);
            answer(ans);
            return;
        }
        if (sum<a)
            l=mid+1;
        else
            r=mid-1;
    }
    long long pre=0;
    for (long long i=1; i<k; i++)
    {
        if (!x[i])
            x[i]=skim(i);
        pre+=x[i];
    }
    l=k, r=n;
    while (l<=r)
    {
        long long mid=(l+r)/2;
        if (!x[mid])
            x[mid]=skim(mid);
        if (a<=pre+x[mid] && pre+x[mid]<=a*2)
        {
            for (long long i=1; i<k; i++)
                ans.push_back(i);
            ans.push_back(mid);
            answer(ans);
            return;
        }
        if (pre+x[mid]<a)
            l=mid+1;
        else
            r=mid-1;
    }
    impossible();
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20