제출 #1038456

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
 
#pragma GCC optimize("O3")
#define endl '\n'
#define db double
#define ll long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
 
//
// --- 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.
//
 
bool check(ll sum, ll a){
    return (sum >= a && sum <= 2*a); 
}
 
void solve(int n, int k, long long a, int s) 
{
    vector <ll> v(n+1, -1);
    vector <int> ans;
    ll sum = 0; 

    map <int, int> mp; 
 
    for(int i = 1; i <= k; i++){
        v[i] = skim(i);
        ans.push_back(i); 
        sum += v[i]; 
        mp[i] = 1; 
    }
 
    if(sum > 2*a){
        impossible(); 
        return;
    }else if(check(sum, a)){
        answer(ans); 
        return;
    }

    reverse(all(ans));
 
    int l = k, r = n+1; 
    while (abs(l - r) != 1)
    {
        int mid = (l + r) / 2; 
 
        if(v[mid] == -1){
            v[mid] = skim(mid);
        }
 
        ll tmp = sum + (v[mid] - ans[0]);
        if(tmp >= sum && tmp <= 2*a)
            l = mid; 
        else 
            r = mid; 
    }
 
    priority_queue <pair<ll, int>> pq, px; 
 
    for(int i = 0; i < k; i++) if(l - i >= 0){
        if(v[l-i] == -1){
            v[l-i] = skim(l-i); 
        }
        pq.push({ v[l-i], l-i });
    }
 
    for(auto& u : ans){
        if(check(sum, a)) break;

        while (!px.empty()){
            pq.push(px.top()); 
            px.pop(); 
        } 
        
        while (!pq.empty()){
            if(mp[pq.top().sd] == 1){
                px.push(pq.top());
                pq.pop(); 
            }
            else break;
        }
        
        if(pq.empty()) continue;
        if(pq.top().fs <= v[u]) continue;
        
        mp[u] = 0; 
        sum = sum + (pq.top().fs - v[u]);
        u = pq.top().sd; mp[u] = 1; 
        pq.pop(); 
    }
 
    if(check(sum, a))
        answer(ans); 
    else 
        impossible(); 
}

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