Submission #967725

#	Time	Username	Problem	Language	Result	Execution time	Memory
967725		qwusha	A Difficult(y) Choice (BOI21_books)	C++17	45 / 100	1 ms	1368 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ll mod = 1e18 + 7;
const ld eps = 1e-8;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const ll inf = 1e18;

/*
ll skim (ll v) {
    cout << v << endl;
    ll x;
    cin >> x;
    return x;
}


void answer(vector<ll> a) {
    for (ll i = 0; i < a.size(); i++) {
        cout << a[i] << ' ';
    }
    exit(0);
}



void impossible() {
    cout << "imp" << '\n';
    exit(0);
}*/

void answerik(set<ll> indi) {
    vector<int> res;
    for (auto j : indi)
        res.push_back(j);
    answer(res);
}


void solve(int n, int k, ll A, int S) {
    ll l = 0, r = n + 1;
    vector<ll> known(n + 1, -1);
    while (r - l > 1) {
        ll m = (l + r) / 2;
        ll x = skim(m);
        known[m] = x;
        if (x < A / k) {
            l = m;
        } else
            r = m;
    }
    if (r == n + 1) {
        impossible();
    }
    set<ll> ind = {r};
    ll cnt = 1;
    ll curi = r;
    while (cnt < k && curi < n) {
        curi++;
        if (known[curi] == -1) {
            ll x = skim(curi);
            known[curi] = x;
        }
        if (known[curi] > A * 2)
            break;
        cnt++;
        ind.insert(curi);
    }
    ll right = curi;
    curi = r;
    while (cnt < k && curi > 1) {
        curi--;
        if (known[curi] == -1) {
            ll x = skim(curi);
            known[curi] = x;
        }
        if (known[curi] > A * 2)
            break;
        cnt++;
        ind.insert(curi);
    }
    ll left = curi;
    if (cnt < k) {
        impossible();
    }
    ll sum = 0;
    vector<bool> taken(n + 1), evertaken(n + 1);
    for (ll i : ind) {
        sum += known[i];
        taken[i] = 1;
        evertaken[1];
    }
    bool ok = 0;
    while (!ok) {
        for (auto i : ind)
            evertaken[i] = 1;
        if (A <= sum && sum <= 2 * A) {
            answerik(ind);
        }
        left = *ind.begin();
        auto t = ind.end();
        t--;
        right = *t;
        if (sum > 2 * A) {
            ll maxi = 0;
            pair<ll, ll> pm;
            for (ll i = max(1ll, left - 1); i < right; i++) {
                if (known[i] == -1) {
                    ll x = skim(i);
                    known[i] = x;
                }
                if (taken[i])
                    continue;
                for (ll j : ind) {
                    if (sum - known[j] + known[i] >= A && sum - known[j] + known[i] <= 2 * A) {
                        sum += known[i] - known[j];
                        taken[j] = 0;
                        taken[i] = 1;
                        ind.insert(i);
                        ind.erase(j);
                        answerik(ind);
                    }
                    if (known[j] - known[i] > maxi) {
                        maxi = known[j] - known[i];
                        pm = {j, i};
                    }
                }
            }
            if (maxi == 0) {
                impossible();
            }
            if (evertaken[pm.fi] && evertaken[pm.se]) {
                impossible();
            }
            taken[pm.fi] = 0;
            taken[pm.se] = 1;
            sum += known[pm.se] - known[pm.fi];
            ind.erase(pm.fi);
            ind.insert(pm.se);
        } else {
            ll maxi = 0;
            pair<ll, ll> pm;
            for (ll i = left + 1; i <= min((ll)n, right + 1); i++) {
                if (known[i] == -1) {
                    ll x = skim(i);
                    known[i] = x;
                }
                if (taken[i])
                    continue;
                for (ll j : ind) {
                    if (sum - known[j] + known[i] >= A && sum - known[j] + known[i] <= 2 * A) {
                        sum += known[i] - known[j];
                        taken[j] = 0;
                        taken[i] = 1;
                        ind.insert(i);
                        ind.erase(j);
                        answerik(ind);
                    }
                    if (known[i] - known[j] > maxi) {
                        maxi = known[i] - known[j];
                        pm = {j, i};
                    }
                }
            }
            if (maxi == 0) {
                impossible();
            }
            if (evertaken[pm.fi] && evertaken[pm.se]) {
                impossible();
            }
            taken[pm.fi] = 0;
            taken[pm.se] = 1;
            sum += known[pm.se] - known[pm.fi];
            ind.erase(pm.fi);
            ind.insert(pm.se);
        }
    }

}

/*
signed main() {
    //solve(15, 3, 42, 8);
}
*/

• 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