| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1275980 | sphoabinh1980 | 선물 (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include <vector>
#include <algorithm>
using namespace std;
void buy_souvenirs(int N, long long P0) {
// Sinh tất cả dãy P khả dĩ: giảm dần, P[0]=P0, 1<=P[i]<=10
vector<vector<int>> candidates;
vector<int> cur = { (int)P0 };
function<void()> generate = [&]() {
if ((int)cur.size() == N) {
candidates.push_back(cur);
return;
}
int last = cur.back();
for (int x = last - 1; x >= 1; --x) {
cur.push_back(x);
generate();
cur.pop_back();
}
};
generate();
vector<int> total_bought(N, 0);
// Duyệt để xác định đúng dãy P
while (candidates.size() > 1) {
// Chọn M = 1 (luôn an toàn vì P[N-1] >= 1, và nếu không mua -> skip, nhưng đề bài cấm)
// Thay vào đó, chọn M = P0 - 1 (luôn >= P[N-1])
long long M = P0 - 1;
// Nhưng để phân biệt, chọn M nhỏ nhất có thể phân biệt các candidate
// Đơn giản: thử M = 1,2,...,P0-1 đến khi phân biệt được
bool found = false;
for (M = 1; M < P0; ++M) {
// Mô phỏng transaction(M) trên tất cả candidate
vector<vector<int>> results;
for (auto& cand : candidates) {
long long coins = M;
vector<int> bought;
for (int i = 0; i < N; ++i) {
if (coins >= cand[i]) {
coins -= cand[i];
bought.push_back(i);
}
}
results.push_back(bought);
}
// Kiểm tra xem có ít nhất 2 kết quả khác nhau
bool all_same = true;
for (int i = 1; i < (int)results.size(); ++i) {
if (results[i] != results[0]) {
all_same = false;
break;
}
}
if (!all_same) {
// Dùng M này để truy vấn thật
auto real_res = transaction(M);
const vector<int>& real_bought = real_res.first;
// Cập nhật total_bought
for (int t : real_bought) {
total_bought[t]++;
}
// Lọc candidates
vector<vector<int>> new_candidates;
for (int i = 0; i < (int)candidates.size(); ++i) {
if (results[i] == real_bought) {
new_candidates.push_back(candidates[i]);
}
}
candidates = new_candidates;
found = true;
break;
}
}
if (!found) break;
}
// Bây giờ candidates[0] là dãy P đúng
vector<int> P = candidates[0];
// Mua đủ số lượng còn thiếu
for (int i = 1; i < N; ++i) {
int need = i - total_bought[i];
for (int j = 0; j < need; ++j) {
transaction(P[i]);
}
}
}