Submission #783532

#	Time	Username	Problem	Language	Result	Execution time	Memory
783532		Hanksburger	A Difficult(y) Choice (BOI21_books)	C++17	80 / 100	2 ms	336 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)
{
    if (s>=170)
    {
        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();
    }
    else
    {
        for (long long i=1; i<=k; i++)
            x[i]=skim(i);
        for (long long i=n-k+1; i<=n; i++)
            x[i]=skim(i);
        long long sum[11]={};
        for (long long i=0; i<=k; i++)
        {
            for (long long j=1; j<=k-i; j++)
                sum[i]+=x[j];
            for (long long j=n-i+1; j<=n; j++)
                sum[i]+=x[j];
        }
        long long ind=k+1;
        for (long long i=0; i<=k; i++)
        {
            if (a<=sum[i] && sum[i]<=a*2)
            {
                for (long long j=1; j<=k-i; j++)
                    ans.push_back(j);
                for (long long j=n-i+1; j<=n; j++)
                    ans.push_back(j);
                answer(ans);
                return;
            }
            else if (sum[i]>a*2)
            {
                ind=i;
                break;
            }
        }
        if (ind==0 || ind==k+1)
        {
            impossible();
            return;
        }
        long long pre=0;
        for (long long i=1; i<=k-ind; i++)
            pre+=x[i];
        for (long long i=n-ind+2; i<=n; i++)
            pre+=x[i];
        long long l=k-ind+1, r=n-ind+1;
        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-ind; i++)
                    ans.push_back(i);
                for (long long i=n-ind+2; i<=n; 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: 20 / 20
• Subtask 7: 0 / 20