Submission #573643

#	Time	Username	Problem	Language	Result	Execution time	Memory
573643		talant117408	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	0 ms	208 KiB

books

#include "books.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

void solve(int n, int k, long long a, int s) {
    if (1) {
        if (skim(1) > a*2) {
            impossible();
            return;
        }
        int l = 1, r = n, highest = 0;
        while (l <= r) {
            int mid = (l+r) >> 1;
            auto res = skim(mid);
            if (res <= 2*a) {
                highest = max(highest, mid);
                l = mid+1;
            }
            else {
                r = mid-1;
            }
        }
        ll sum = 0;
        vector <int> v;
        if (highest >= k) {
            for (int i = highest; i > highest-k; i--) {
                sum += skim(i);
                v.pb(i);
            }
            if (a <= sum && sum <= a*2) {
                answer(v);
                return;
            }
            else if (a < sum) {
                impossible();
                return;
            }
        }
    }
    int ans = -1;
    int l = 1, r = n-k+1;
    while (l <= r) {
        int mid = (l+r) >> 1;
        ll sum = 0;
        for (int i = mid; i < mid+k; i++) {
            sum += skim(i);
        }
        if (a <= sum && sum <= a*2) {
            ans = mid;
            break;
        }
        else if (sum < a) {
            l = mid+1;
        }
        else {
            r = mid-1;
        }
    }
    if (ans == -1) impossible();
    else {
        vector <int> v;
        for (int i = ans; i < ans+k; i++) {
            v.pb(i);
        }
        answer(v);
    }
}
//~ 15 3 42 170
//~ 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

• 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