| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 967700 | qwusha | A Difficult(y) Choice (BOI21_books) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 + 1) / 2 && 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);
for (ll i : ind) {
sum += known[i];
taken[i] = 1;
}
bool ok = 0;
while (!ok) {
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();
}
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(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();
}
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);
}
*/