제출 #1162506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162506		KK_1729	A Difficult(y) Choice (BOI21_books)	C++20	60 / 100	0 ms	408 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}


// using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int K, long long A, int S) {
    int pos = 0;
    for (int i = 16; i >= 0; i--){
        if ((pos|(1 << i)) > N) continue;
        int t = pos|(1 << i);
        if (skim(t) <= A) pos |= (1 << i);
    }
    if (pos == 0){
        impossible();
        return;
    }
    long long u = 0ll;
    if (pos < N) u = skim(pos+1);
    else u = 2e18;

    vector<pair<long long, int>> a;
    if (pos >= K){
        FOR(i,1,K+1){
            a.pb({skim(i), i});
        }
        long long sum = 0ll;
        FOR(i,0,K-1) sum += a[i].first;
        if (sum+u <= 2ll*A){
            vector<int> ans = {};
            FOR(i,1,K) ans.pb(i);
            ans.pb(pos+1);
            answer(ans);
            return;
        }
    }

    if (pos <= 2*K){
        FOR(i,K+1,pos+1) a.pb({skim(i), i});

    }else{
        FOR(i,pos-K+1,pos+1) a.pb({skim(i), i});
    }
    

    int g = a.size();
        int i = 0;
        while (i+K-1 < g){
            long long curr = 0ll;
            FOR(j,i,i+K) curr += a[j].first;
            if (curr >= A && curr <= 2ll*A){
                vector<int> ans = {};
                FOR(h,i,i+K) ans.pb(a[h].second);
                answer(ans);
                return;
            }
            i++;
        }
    impossible();
}

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