Submission #406834

#	Time	Username	Problem	Language	Result	Execution time	Memory
406834		Ruxandra985	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	3 ms	1156 KiB

books

#include<bits/stdc++.h>
#include "books.h"
using namespace std;

long long skim(int pos);
void answer(vector<int> v);
void impossible();

long long v[100010];
int w[100010];

void solve(int n, int k, long long a, int s) {
    int i , st , dr , mid , elem;
    long long sum;
    vector <int> ans;
    sum = 0;
    for (i = 1 ; i <= n ; i++){
        v[i] = -1;
        if (i <= k){
            v[i] = skim(i);
            sum += v[i];
        }
    }

    if (sum > 2 * a){
        impossible();
        return;
    }
    else if (sum >= a && sum <= 2 * a){
        for (i = 1 ; i <= k ; i++)
            ans.push_back(i);
        answer(ans);
        return;
    }

    /// sum < a

    st = k + 1;
    dr = n;
    while (st <= dr){
        mid = (st + dr)/2;
        v[mid] = skim(mid);
        if (v[mid] < a)
            st = mid + 1;
        else dr = mid - 1;
    }

    if (st != n + 1 && sum - v[k] + v[st] <= 2 * a){
        for (i = 1 ; i < k ; i++)
            ans.push_back(i);
        ans.push_back(st);
        answer(ans);
        return;
    }

    /// trb sa iei elemente doar intre 1 si st - 1, toate < a

    n = st - 1;
    elem = 0;
    for (i = 1 ; i <= k ; i++)
        w[++elem] = i;

    for (i = max(k , n - k + 1) ; i <= n ; i++)
        w[++elem] = i;

    st = 1;
    dr = k;
    while ((a > sum || sum > 2 * a) && dr < elem){
        sum -= v[w[st]];
        st++;
        dr++;
        if (v[w[dr]] == -1)
            v[w[dr]] = skim(w[dr]);
        sum += v[w[dr]];

        if (a <= sum && sum <= 2 * a){

            for (i = st ; i <= dr ; i++)
                ans.push_back(w[i]);
            answer(ans);
            return;

        }

    }


    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