#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);
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((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();
}
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);
}
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Execution timed out |
3055 ms |
344 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Execution timed out |
3092 ms |
344 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1244 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1244 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1368 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1368 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1368 KB |
Output is correct |
17 |
Correct |
1 ms |
1368 KB |
Output is correct |
18 |
Correct |
1 ms |
1244 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Correct |
1 ms |
1112 KB |
Output is correct |
24 |
Correct |
1 ms |
1412 KB |
Output is correct |
25 |
Correct |
1 ms |
1368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1244 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1368 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1368 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1368 KB |
Output is correct |
17 |
Correct |
1 ms |
1368 KB |
Output is correct |
18 |
Correct |
1 ms |
1244 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Correct |
1 ms |
1112 KB |
Output is correct |
24 |
Correct |
1 ms |
1412 KB |
Output is correct |
25 |
Correct |
1 ms |
1368 KB |
Output is correct |
26 |
Correct |
1 ms |
1368 KB |
Output is correct |
27 |
Correct |
1 ms |
1112 KB |
Output is correct |
28 |
Correct |
1 ms |
1368 KB |
Output is correct |
29 |
Correct |
1 ms |
1112 KB |
Output is correct |
30 |
Correct |
1 ms |
1368 KB |
Output is correct |
31 |
Correct |
1 ms |
1112 KB |
Output is correct |
32 |
Correct |
1 ms |
1112 KB |
Output is correct |
33 |
Correct |
1 ms |
1236 KB |
Output is correct |
34 |
Correct |
1 ms |
1112 KB |
Output is correct |
35 |
Correct |
1 ms |
1368 KB |
Output is correct |
36 |
Correct |
1 ms |
1112 KB |
Output is correct |
37 |
Correct |
1 ms |
1204 KB |
Output is correct |
38 |
Correct |
1 ms |
1368 KB |
Output is correct |
39 |
Correct |
1 ms |
1112 KB |
Output is correct |
40 |
Correct |
1 ms |
1112 KB |
Output is correct |
41 |
Correct |
1 ms |
1112 KB |
Output is correct |
42 |
Correct |
1 ms |
1368 KB |
Output is correct |
43 |
Correct |
1 ms |
1112 KB |
Output is correct |
44 |
Correct |
1 ms |
1408 KB |
Output is correct |
45 |
Correct |
1 ms |
1112 KB |
Output is correct |
46 |
Correct |
1 ms |
1400 KB |
Output is correct |
47 |
Correct |
1 ms |
1112 KB |
Output is correct |
48 |
Correct |
1 ms |
1112 KB |
Output is correct |
49 |
Execution timed out |
3069 ms |
1112 KB |
Time limit exceeded |
50 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1244 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1368 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1368 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1368 KB |
Output is correct |
17 |
Correct |
1 ms |
1368 KB |
Output is correct |
18 |
Correct |
1 ms |
1244 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Correct |
1 ms |
1112 KB |
Output is correct |
24 |
Correct |
1 ms |
1412 KB |
Output is correct |
25 |
Correct |
1 ms |
1368 KB |
Output is correct |
26 |
Correct |
1 ms |
1368 KB |
Output is correct |
27 |
Correct |
1 ms |
1112 KB |
Output is correct |
28 |
Correct |
1 ms |
1368 KB |
Output is correct |
29 |
Correct |
1 ms |
1112 KB |
Output is correct |
30 |
Correct |
1 ms |
1368 KB |
Output is correct |
31 |
Correct |
1 ms |
1364 KB |
Output is correct |
32 |
Correct |
1 ms |
1368 KB |
Output is correct |
33 |
Correct |
1 ms |
1368 KB |
Output is correct |
34 |
Correct |
1 ms |
1240 KB |
Output is correct |
35 |
Correct |
1 ms |
1236 KB |
Output is correct |
36 |
Correct |
1 ms |
1368 KB |
Output is correct |
37 |
Correct |
1 ms |
1448 KB |
Output is correct |
38 |
Correct |
1 ms |
1112 KB |
Output is correct |
39 |
Correct |
1 ms |
1368 KB |
Output is correct |
40 |
Correct |
1 ms |
1112 KB |
Output is correct |
41 |
Correct |
1 ms |
1232 KB |
Output is correct |
42 |
Correct |
1 ms |
1112 KB |
Output is correct |
43 |
Correct |
1 ms |
1064 KB |
Output is correct |
44 |
Correct |
1 ms |
1112 KB |
Output is correct |
45 |
Correct |
1 ms |
1368 KB |
Output is correct |
46 |
Correct |
1 ms |
1368 KB |
Output is correct |
47 |
Correct |
1 ms |
1236 KB |
Output is correct |
48 |
Correct |
1 ms |
1404 KB |
Output is correct |
49 |
Correct |
1 ms |
1108 KB |
Output is correct |
50 |
Correct |
1 ms |
1112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1112 KB |
Output is correct |
2 |
Correct |
1 ms |
1244 KB |
Output is correct |
3 |
Correct |
1 ms |
1112 KB |
Output is correct |
4 |
Correct |
1 ms |
1112 KB |
Output is correct |
5 |
Correct |
1 ms |
1112 KB |
Output is correct |
6 |
Correct |
1 ms |
1112 KB |
Output is correct |
7 |
Correct |
1 ms |
1112 KB |
Output is correct |
8 |
Correct |
1 ms |
1112 KB |
Output is correct |
9 |
Correct |
1 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1112 KB |
Output is correct |
11 |
Correct |
1 ms |
1112 KB |
Output is correct |
12 |
Correct |
1 ms |
1368 KB |
Output is correct |
13 |
Correct |
1 ms |
1112 KB |
Output is correct |
14 |
Correct |
1 ms |
1368 KB |
Output is correct |
15 |
Correct |
1 ms |
1112 KB |
Output is correct |
16 |
Correct |
1 ms |
1368 KB |
Output is correct |
17 |
Correct |
1 ms |
1368 KB |
Output is correct |
18 |
Correct |
1 ms |
1244 KB |
Output is correct |
19 |
Correct |
1 ms |
1112 KB |
Output is correct |
20 |
Correct |
1 ms |
1112 KB |
Output is correct |
21 |
Correct |
1 ms |
1112 KB |
Output is correct |
22 |
Correct |
1 ms |
1112 KB |
Output is correct |
23 |
Correct |
1 ms |
1112 KB |
Output is correct |
24 |
Correct |
1 ms |
1412 KB |
Output is correct |
25 |
Correct |
1 ms |
1368 KB |
Output is correct |
26 |
Correct |
1 ms |
1368 KB |
Output is correct |
27 |
Correct |
1 ms |
1112 KB |
Output is correct |
28 |
Correct |
1 ms |
1368 KB |
Output is correct |
29 |
Correct |
1 ms |
1112 KB |
Output is correct |
30 |
Correct |
1 ms |
1368 KB |
Output is correct |
31 |
Correct |
1 ms |
1112 KB |
Output is correct |
32 |
Correct |
1 ms |
1112 KB |
Output is correct |
33 |
Correct |
1 ms |
1236 KB |
Output is correct |
34 |
Correct |
1 ms |
1112 KB |
Output is correct |
35 |
Correct |
1 ms |
1368 KB |
Output is correct |
36 |
Correct |
1 ms |
1112 KB |
Output is correct |
37 |
Correct |
1 ms |
1204 KB |
Output is correct |
38 |
Correct |
1 ms |
1368 KB |
Output is correct |
39 |
Correct |
1 ms |
1112 KB |
Output is correct |
40 |
Correct |
1 ms |
1112 KB |
Output is correct |
41 |
Correct |
1 ms |
1112 KB |
Output is correct |
42 |
Correct |
1 ms |
1368 KB |
Output is correct |
43 |
Correct |
1 ms |
1112 KB |
Output is correct |
44 |
Correct |
1 ms |
1408 KB |
Output is correct |
45 |
Correct |
1 ms |
1112 KB |
Output is correct |
46 |
Correct |
1 ms |
1400 KB |
Output is correct |
47 |
Correct |
1 ms |
1112 KB |
Output is correct |
48 |
Correct |
1 ms |
1112 KB |
Output is correct |
49 |
Execution timed out |
3069 ms |
1112 KB |
Time limit exceeded |
50 |
Halted |
0 ms |
0 KB |
- |