Submission #446907

#	Time	Username	Problem	Language	Result	Execution time	Memory
446907		wiwiho	A Difficult(y) Choice (BOI21_books)	C++14	60 / 100	3 ms	1032 KiB

books

#include <bits/stdc++.h>

#include "books.h"

#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))

using namespace std;

typedef long long ll;
const ll MAX = 1LL << 60;

using pii = pair<int, int>;

void ans(int st, int k){
    vector<int> v(k);
    for(int i = 0; i < k; i++) v[i] = st + i;
    answer(v);
}

vector<ll> x;
ll query(int i){
    if(x[i] == -1) x[i] = skim(i);
    return x[i];
}

ll qrange(int l, int r){
    ll sum = 0;
    for(int i = l; i <= r; i++) sum += query(i);
    return sum;
}

void solve(int n, int k, ll A, int S){

    x.resize(n + 1, -1);

    int l = 1, r = n - k + 1;
    while(l < r){
        int m = (l + r) / 2;
        if(qrange(m, m + k - 1) < A) l = m + 1;
        else r = m;
    }

    ll sum = qrange(l, l + k - 1);
    if(A <= sum && sum <= 2 * A) ans(l, k);

    l = 1, r = n;
    while(l < r){
        int m = (l + r) / 2;
        if(query(m) >= A) r = m;
        else l = m + 1;
    }
    if(k - 1 >= l || query(l) < A || query(l) > 2 * A) impossible();
    sum = qrange(1, k - 1) + query(l);
    if(A <= sum && sum <= 2 * A){
        vector<int> v;
        for(int i = 1; i < k; i++) v.eb(i);
        v.eb(l);
        answer(v);
    }
    
    impossible();
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20