Submission #773919

#	Time	Username	Problem	Language	Result	Execution time	Memory
773919		ZHIRDILBILDIZ	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	2 ms	1744 KiB

books

#include<bits/stdc++.h>
#include"books.h"
#define ll long long
#define fi first
#define se second
using namespace std ;
void solve(int n, int k, ll a, int s)
{
    vector<int> ans, md ;
    ll x[n + 1] = {}, pref[n + 1] = {} ;
    for(int i = 1 ; i <= k ; i++)
    {
        x[i] = skim(i) ;
        pref[i] = pref[i - 1] + x[i] ;
    }
    if(pref[k] > 2ll * a)
        impossible() ;
    if(a <= pref[k] && pref[k] <= 2ll * a)
    {
        for(int i = 1 ; i <= k ; i++)
            ans.push_back(i) ;
        answer(ans) ;
    }
    ll l = 0, r = n + 1 ;
    while(l + 1 < r)
    {
        ll mid = (l + r) >> 1ll, num = x[mid] ;
        if(!num)
        {
            num = skim(mid) ;
            x[mid] = num ;
        }
        if(num < a)l = mid ;
        else r = mid ;
    }
    if(r < k)impossible() ;
    if(r != n + 1 && x[r] + pref[k - 1] <= 2ll * a)
    {
        for(int i = 1 ; i < k ; i++)
            ans.push_back(i) ;
        ans.push_back(r) ;
        answer(ans) ;
    }
    if(r == n + 1)r = n ;
    ll sum = pref[k] ;
    for(int i = 1 ; i <= k ; i++)
        ans.push_back(i) ;
    for(int j = r - k ; j < r ; j++)
    {
        if(!x[j])x[j] = skim(j) ;
        md.push_back(x[j]) ;
    }
    for(int j = k - 1 ; j > 0 ; j--)
    {
        sum -= ans[j] ;
        sum += md[j] ;
        ans[j] = r - k + j ;
        if(a <= sum && sum <= 2ll * a)
            answer(ans) ;
    }
    impossible() ;
}
//4 часа

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