oj.uz

Submission #967725

# Submission time Handle Problem Language Result Execution time Memory
967725 2024-04-22T17:05:57 Z qwusha A Difficult(y) Choice (BOI21_books) C++17
45 / 100
 1 ms 1368 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 0 ms 344 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1368 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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1368 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 1112 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1112 KB Output is correct
19 Correct 1 ms 1236 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 1228 KB Output is correct
24 Correct 1 ms 1368 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1368 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 1112 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1112 KB Output is correct
19 Correct 1 ms 1236 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 1228 KB Output is correct
24 Correct 1 ms 1368 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 1 ms 1368 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 1112 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 1112 KB Output is correct
34 Correct 1 ms 1112 KB Output is correct
35 Correct 1 ms 1112 KB Output is correct
36 Correct 1 ms 1232 KB Output is correct
37 Correct 1 ms 1112 KB Output is correct
38 Correct 1 ms 1112 KB Output is correct
39 Correct 1 ms 1112 KB Output is correct
40 Correct 1 ms 1236 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 1232 KB Output is correct
45 Correct 1 ms 1112 KB Output is correct
46 Correct 1 ms 1112 KB Output is correct
47 Correct 1 ms 1236 KB Output is correct
48 Correct 1 ms 1368 KB Output is correct
49 Incorrect 1 ms 1112 KB Incorrect
50 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1368 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 1112 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1112 KB Output is correct
19 Correct 1 ms 1236 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 1228 KB Output is correct
24 Correct 1 ms 1368 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 1 ms 1112 KB Output is correct
28 Correct 1 ms 1236 KB Output is correct
29 Correct 1 ms 1112 KB Output is correct
30 Correct 1 ms 1112 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 1108 KB Output is correct
34 Correct 1 ms 1364 KB Output is correct
35 Correct 1 ms 1368 KB Output is correct
36 Correct 1 ms 1236 KB Output is correct
37 Correct 1 ms 1112 KB Output is correct
38 Correct 1 ms 1112 KB Output is correct
39 Correct 1 ms 1232 KB Output is correct
40 Correct 1 ms 1368 KB Output is correct
41 Correct 1 ms 1112 KB Output is correct
42 Correct 1 ms 1240 KB Output is correct
43 Correct 1 ms 1112 KB Output is correct
44 Correct 1 ms 1112 KB Output is correct
45 Correct 1 ms 1112 KB Output is correct
46 Correct 1 ms 1236 KB Output is correct
47 Correct 1 ms 1228 KB Output is correct
48 Correct 1 ms 1112 KB Output is correct
49 Correct 1 ms 1368 KB Output is correct
50 Correct 1 ms 1112 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1368 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 1112 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1112 KB Output is correct
19 Correct 1 ms 1236 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 1228 KB Output is correct
24 Correct 1 ms 1368 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 1 ms 1368 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 1112 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 1112 KB Output is correct
34 Correct 1 ms 1112 KB Output is correct
35 Correct 1 ms 1112 KB Output is correct
36 Correct 1 ms 1232 KB Output is correct
37 Correct 1 ms 1112 KB Output is correct
38 Correct 1 ms 1112 KB Output is correct
39 Correct 1 ms 1112 KB Output is correct
40 Correct 1 ms 1236 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 1232 KB Output is correct
45 Correct 1 ms 1112 KB Output is correct
46 Correct 1 ms 1112 KB Output is correct
47 Correct 1 ms 1236 KB Output is correct
48 Correct 1 ms 1368 KB Output is correct
49 Incorrect 1 ms 1112 KB Incorrect
50 Halted 0 ms 0 KB -