# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
560184 | Ooops_sorry | A Difficult(y) Choice (BOI21_books) | C++14 | 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>
using namespace std;
#ifndef LOCAL
#include books.h
#else
long long skim(int i) {
cout << "? " << i << endl;
int val;
cin >> val;
return val;
}
void answer(vector<int> v) {
for (auto to : v) {
cout << to << ' ';
}
cout << endl;
}
void impossible() {
cout << "NO WAY" << endl;
}
#endif // LOCAL
#define pb push_back
#define ll long long
void solve(int n, int k, ll a, int s) {
int l = -1, r = n;
while (r - l > 1) {
int mid = (r + l) / 2;
if (skim(mid + 1) >= a) {
r = mid;
} else {
l = mid;
}
}
ll sum = 0;
vector<int> arr;
for (int j = 0; j < k - 1; j++) {
sum += skim(j + 1);
arr.pb(j + 1);
}
vector<int> rem_arr = arr;
ll val = skim(k), rem_sum = sum;
sum += val;
arr.pb(k);
if (a <= sum && sum <= 2 * a) {
answer(arr);
return;
}
if (r >= k) {
vector<int> nw;
for (int j = 0; j < k; j++) {
sum -= skim(k - j);
sum += skim(r - j);
nw.pb(r - j);
arr.pop_back();
if (a <= sum && sum <= 2 * a) {
for (auto to : nw) arr.pb(to);
answer(arr);
return;
}
}
}
sum = rem_sum, arr = rem_arr;
if (r < n) {
if (r >= k - 1) {
ll valr = skim(r + 1);
sum += valr;
if (a <= sum && sum <= 2 * a) {
arr.pb(r + 1);
answer(arr);
return;
}
}
}
impossible();
}
#ifdef LOCAL
signed main() {
int n, k, s;
long long a;
cin >> n >> k >> a >> s;
solve(n, k, a, s);
}
#endif // LOCAL