Submission #1301449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301449		efeg	A Difficult(y) Choice (BOI21_books)	C++20	60 / 100	2 ms	1192 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

#define pb push_back; 
#define all(v) v.begin(),v.end()
using i64 = long long; 
template<typename T>
using vec = vector<T>;


vec<i64> x(1e5 + 100,-1); 
i64 get(int idx){
    if (x[idx] != -1) return x[idx]; 
    return x[idx] = skim(idx); 
}

void solve(int N, int K, long long A, int S) {
    vec<int> ansvec(K); 
    i64 sm = 0; 
    for (int i = 1; i < K; i++){
        sm += get(i); 
        ansvec[i-1] = i; 
    }   

    int s = K,e = N; 
    while (s <= e){
        int m = (s + e) / 2; 
        if (sm + get(m) > 2 * A) e = m-1; 
        else if (sm + get(m) < A) s = m+1; 
        else {
            ansvec[K-1] = m; 
            answer(ansvec); 
        }
    }

    s = 1,e = N - K + 1; 
    while (s <= e){
        int m = (s+e) / 2; 
        i64 curr = 0; 
        for (int i = m; i < m + K; i++) curr += get(i); 
        if (curr > 2 * A) e = m-1; 
        else if (curr < A) s = m+1; 
        else {
            iota(all(ansvec),m); 
            answer(ansvec); 
        }
    }

    impossible(); 
}

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