Submission #939551

#	Time	Username	Problem	Language	Result	Execution time	Memory
939551		LucaIlie	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	1116 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;

const int MAX_N = 1e5;
long long difficulty[MAX_N + 1];
int n, m, k, q;
long long a;

long long d( int i ) {
    if ( difficulty[i] == 0 )
        difficulty[i] = skim( i );
    return difficulty[i];
}

void findM() {
    int l = 0, r = n + 1;
    while ( r - l > 1 ) {
        int mid = (l + r) / 2;

        if ( d( mid ) >= a )
            r = mid;
        else
            l = mid;
    }
    m = l;
}

void checkLarge() {
    if ( m != n ) {
        long long s = d( m + 1 );
        vector<int> ans;
        ans.push_back( m + 1 );
        for ( int i = 1; i < k; i++ ) {
            s += d( i );
            ans.push_back( i );
        }
        if ( s <= 2 * a ) {
            answer( ans );
            return;
        }
    }
}

void solve( int N, int K, long long A, int Q ) {
    n = N;
    k = K;
    a = A;
    q = Q;

    findM();
    if ( m == 0 ) {
        impossible();
        return;
    }
    checkLarge();
    if ( m < k ) {
        impossible();
        return;
    }

    for ( int p = 0; p <= k; p++ ) {
        vector<int> ans;
        long long s = 0;
        for ( int i = 1; i <= p; i++ ) {
            s += d( i );
            ans.push_back( i );
        }
        for ( int i = m; i >= m - (k - p) + 1; i-- ) {
            s += d( i );
            ans.push_back( i );
        }

        if ( a <= s && s <= 2 * a ) {
            answer( ans );
            return;
        }
    }
    impossible();
}

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