Submission #406489

#	Time	Username	Problem	Language	Result	Execution time	Memory
406489		Ruxandra985	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	2 ms	300 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];
 
void solve(int n, int k, long long a, int s) {
    int i , st , dr , mid;
    long long sum;
    vector <int> ans;
    sum = 0;
    for (i = 1 ; i <= n ; i++){
        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;
    st = k;
    dr = n + 1;
    while (st > 1){
 
        sum -= v[st];
        st--;
        dr--;
 
        if (v[dr] == -1)
            v[dr] = skim(dr);
        sum += v[dr];
 
        if (sum >= a && sum <= 2 * a){
 
            for (i = 1 ; i <= st ; i++)
                ans.push_back(i);
            for (i = dr ; i <= n ; i++)
                ans.push_back(i);
 
            answer(ans);
            return;
 
        }
 
    }
    impossible();
 
 
}

• 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