Submission #1038447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038447		HorizonWest	A Difficult(y) Choice (BOI21_books)	C++17	25 / 100	6 ms	3668 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;

const ll Inf = 1e18; 

//
// --- 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); 
}

pair<int, int> find(vector <ll> v, ll x, ll y){
    int n = v.size()-1, l = n+1, r = 0; 
    vector <pair<ll, ll>> s(n+2, { 0, Inf });
    for(int i = 1; i <= n; i++){
        s[i].fs = s[i-1].fs; 
        if(v[i] != -1){
            s[i].fs = v[i]; 
        }
    }

    for(int i = n; i >= 1; i--){
        s[i].sd = s[i-1].sd; 
        if(v[i] != -1){
            s[i].sd = v[i]; 
        }
    }

    for(int i = 1; i <= n; i++){
        if(y >= s[i].fs && s[i].sd >= x){
            l = min(l, i); 
            r = max(r, i); 
        }
    }

    return { l, r+1 }; 
}

void solve(int n, int k, long long a, int s) 
{
    vector <ll> v(n+1, -1);
    vector <int> ans;
    ll sum = 0; 

    for(int i = 1; i <= k; i++){
        v[i] = skim(i);
        ans.push_back(i); 
        sum += v[i]; 
    }

    if(sum > 2*a){
        impossible(); 
        return;
    }else if(check(sum, a)){
        answer(ans); 
        return;
    }

    int last = n+1; 

    for(auto& u : ans)
    {
        pair <int, int> t = find(v, v[u]+1, 2*a-sum+v[u]);  
        int l = max(t.fs, k+1), r = min(t.sd, last);  
        if(l > r) break;
        while (abs(l - r) != 1)
        {
            int mid = (l + r) / 2;  

            if(v[mid] == -1){
                v[mid] = skim(mid);
            }

            ll tmp = sum + (v[mid] - v[0]);
            if(tmp >= sum && tmp <= 2*a)
                l = mid; 
            else 
                r = mid; 
        }

        if(v[l] > v[u]){
            sum = sum + (v[l] - v[u]);
            u = l; 
            last = u; 
        }
    }

    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: 0 / 20
• Subtask 7: 0 / 20