제출 #967713

#제출 시각아이디문제언어결과실행 시간메모리
967713qwushaA Difficult(y) Choice (BOI21_books)C++17
45 / 100
3092 ms1448 KiB
#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); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...