Submission #1249761

#TimeUsernameProblemLanguageResultExecution timeMemory
1249761kduckpSouvenirs (IOI25_souvenirs)C++20
0 / 100
0 ms412 KiB
#include "souvenirs.h" #include <bits/stdc++.h> using namespace std; using ll = long long; extern pair<vector<int>, ll> transaction(ll M); // INTERACTIVE! int N; ll P0; vector<ll> price; // Giá của từng loại (từ 0 đến N-1) void buy_souvenirs(int _N, ll _P0) { N = _N; P0 = _P0; price.resize(N); price[0] = P0; // Tìm P[1] đến P[N-1] for (int i = 1; i < N; ++i) { ll low = 1, high = price[i - 1] - 1, res = -1; while (low <= high) { ll mid = (low + high) / 2; auto [items, change] = transaction(mid); if (!items.empty()) { // Mua được ít nhất 1 món res = mid - change; high = mid - 1; } else { low = mid + 1; } } price[i] = res; } // Mua đúng i món loại i (với i >= 1) vector<int> count(N, 0); while (true) { bool done = true; ll money = 0; for (int i = 1; i < N; ++i) { if (count[i] < i) { money += price[i]; done = false; } } if (done) break; if (money >= price[0]) money = price[0] - 1; // Không mua loại 0 auto [items, change] = transaction(money); for (int x : items) { count[x]++; } } }
#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...