제출 #406458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406458		Ruxandra985	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	2 ms	292 KiB

books

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

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

int 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