Submission #404967

#	Time	Username	Problem	Language	Result	Execution time	Memory
404967		nicolaalexandra	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	1 ms	200 KiB

books

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

int n,k,s,i;
long long a;
long long v[DIM],d[DIM];

/*void answer (vector<int> ans){
    for (auto it : ans)
        cout<<it<<" ";
    return;
}
void impossible(){
    cout<<"impossible";
}

long long skim (int poz){
    return v[poz];
}
*/

void solve(int n, int k, long long a, int s) {
    int i;

    int sum = 0;
    for (i=1;i<=k;i++){
        d[i] = skim(i);
        sum += d[i];
    }

    if (sum > 2*a){
        impossible();
        return;
    }

    vector <int> ans;
    if (sum >= a){
        for (i=1;i<=k;i++)
            ans.push_back(i);
        answer(ans);
        return;
    }

    int st = 1, dr = n, poz = n+1;
    while (st <= dr){
        int mid = (st + dr) >> 1;
        if (skim(mid) > a){
            poz = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    if (poz <= n){
        ans.push_back(poz);
        for (i=2;i<=k;i++)
            ans.push_back(poz);
    } else {
        int st = 1, dr = n;
        while (sum < a && dr >= n-k+1){
            sum -= d[st];
            sum += skim(dr);
            st++, dr--;
        }

        if (sum < a){
            impossible();
            return;
        }

        for (i=st;i<=k;i++)
            ans.push_back(i);
        for (i=dr+1;i<=n;i++)
            ans.push_back(i);
    }

    sort (ans.begin(),ans.end());
    answer(ans);


}

• 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