제출 #1064167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064167		vjudge1	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	1 ms	344 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()

const int N = 5e5;

ll n, k, mx;

void solve(int N, int K, long long A, int S) {
    n = N;
    k = K;
    mx = A;
    int lo = 0, hi = n + 1;
    while(lo + 1 < hi){
        int m = (lo + hi) / 2;
        ll x = skim(m);
        if(x > A)
            hi = m;
        else
            lo = m;
    }
    if(hi < k)
        impossible();
    vector<pair<ll, ll>> ha = {};
    if(2 * k < hi){
        for(int i = 1; i <= k; i++){
            ha.pb({i, skim(i)});
        }
        for(int i = hi - k; i < hi; i++){
            ha.pb({i, skim(i)});
        }
    }else{
        for(int i = 1; i < hi; i++)
            ha.pb({i, skim(i)});
    }
    ll sm = 0;
    if(hi <= n){
        sm += skim(hi);
        for(int i = 1; i < k; i++){
            sm += ha[i - 1].S;
        }
        if(sm >= A && sm <= 2 * A){
            vector<int> ret = {};
            for(int i = 1; i < k; i++)
                ret.pb(i);
            ret.pb(hi);
            answer(ret);
            return;
        }
    }
    sm = 0;
    int cur = k - 2;
    while(sm < A){
        cur++;
        if(cur == sz(ha))
            break;
        sm = 0;
        for(int i = cur - k + 1; i <= cur; i++)
            sm += ha[i].S;
    }
    if(cur == sz(ha))
        impossible();
    vector<int> ret = {};
    for(int i = cur - k + 1; i <= cur; i++)
        ret.pb(i + 1);
    answer(ret);
}

• 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