Submission #1183911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183911		tamyte	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	0 ms	408 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
// long long ansA;
// int queries = 0;
// bool imp = false;
// vector<long long> arr;
// void answer(vector<int> a) {
//     long long sum = 0;
//     cout << "ANSWER = ";
//     for (auto& u : a) {
//         cout << u << " ";
//         sum += arr[u - 1];
//     }
//     cout << endl;
//     if (sum >= ansA && sum <= 2 * ansA) {
//         cout << "OK!\n";
//     } else {
//         cout << "WA!\n";
//     }
// }
// void impossible() {
//     if (imp) cout << "OK!\n";
//     else cout << "WA!\n";
// }

// long long skim(int i) {
//     return arr[i - 1];
// }
bool ok(long long sum, long long A) {
    return (sum >= A && sum <= A * 2);
}

void solve(int N, int K, long long A, int S) {
    vector<long long> a;
    long long sum = 0;
    vector<int> ind;
    for (int i = 1; i <= K; ++i) {
        a.push_back(skim(i));
        ind.push_back(i);
        sum += a.back();
    }
    if (ok(sum, A)) {
        answer(ind);
        return;
    }
    int l = K + 1, r = N;
    while (l < r) {
        int m = (l + r) / 2;
        long long ans = skim(m);
        if (ans >= A) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    set<int> st;
    for (int i = max(K + 1, r - K); i <= r; ++i) {
        ind.push_back(i);
        a.push_back(skim(i));
    }
    sort(begin(a), end(a));
    sort(begin(ind), end(ind));
    a.erase(unique(begin(a), end(a)), end(a));
    ind.erase(unique(begin(ind), end(ind)), end(ind));
    // cout << A << ":\n";
    // for (auto& u : a) {
    //     cout << u << " ";
    // }
    // cout << endl;
    
    sum = 0;
    for (int i = 0; i < K - 1; ++i) {
        st.insert(ind[i]);
        sum += a[i];
    }
    for (int j = K - 1; j < a.size(); ++j) {
        sum += a[j];
        st.insert(ind[j]);
        if (ok(sum, A)) {
            answer(vector<int>(begin(st), end(st)));
            return;
        }
        sum -= a[j];
        st.erase(ind[j]);
    }
    st.insert(ind[K - 1]);
    sum += a[K - 1];
    if (ok(sum, A)) {
        answer(vector<int>(begin(st), end(st)));
        return;
    }
    for (int i = K; i < a.size(); ++i) {
        sum -= a[i - K];
        st.erase(st.begin());
        for (int j = i; j < a.size(); ++j) {
            sum += a[j];
            st.insert(ind[j]);
            if (ok(sum, A)) {
                answer(vector<int>(begin(st), end(st)));
                return;
            }
            sum -= a[j];
            st.erase(ind[j]);
        }
        sum += a[i];
        st.insert(ind[i]);
    }
    impossible();
}
// mt19937 rng(time(NULL));
// int main() {
//     ifstream cin("input.txt");
// 	int N, K;
//     long long A;
//     int S;
//     cin >> N >> K >> A >> S;
//     ansA = A;
//     set<long long> st;
//     for (; arr.size() < N;) {
//         long long s;
//         cin >> s;
//         arr.push_back(s);
//         continue;
//         long long n = rng() % 100000 + 1;
//         if (st.count(n)) continue;
//         st.insert(n);
//         arr.push_back(n);
//     }
//     sort(begin(arr), end(arr));
//     // cout << "INITIAL = ";
//     // for (auto& u : arr) {
//     //     cout << u << " ";
//     // }
//     // cout << endl;
//     solve(N, K, A, S);
// }

• 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