Submission #404981

#	Time	Username	Problem	Language	Result	Execution time	Memory
404981		nicolaalexandra	A Difficult(y) Choice (BOI21_books)	C++14	0 / 100	2 ms	292 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(i);
    } 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