Submission #1249426

#TimeUsernameProblemLanguageResultExecution timeMemory
1249426mondellbitSouvenirs (IOI25_souvenirs)C++20
0 / 100
0 ms412 KiB
#include <bits/stdc++.h> #include "souvenirs.h" using namespace std; #define INF (int)1e18 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); int n; const int N = 105; int hidden_p[N]; int counter[N]; pair <vector <int>, long long> transaction(int M){ assert(M >= hidden_p[n - 1] && M < hidden_p[0]); vector <int> bought; for (int i = 0; i < n; i++){ if (M >= hidden_p[i]){ M -= hidden_p[i]; bought.push_back(i); counter[i]++; } } return make_pair(bought, M); } void buy_souvenirs(int N, long long P0){ vector<set<int>> depend(N); vector<int> sum(N); vector<int> ans(N, -1); ans[0] = P0; vector <int> counter(N, 0); while (true){ int left = 0; for (int i = 0; i < N; i++){ left += ans[i] == -1; } if (left == 0){ break; } bool have = false; for (int i = N - 1; i >= 0; i--){ if (ans[i] == -1) have = true; if (ans[i] != -1 && have){ auto [vv, ll] = transaction(ans[i] - 1); set <int> ss; for (auto x : vv) ss.insert(x), counter[x]++; int got = ans[i] - 1 - ll; for (int j = 0; j < N; j++){ if (ans[j] != -1 && ss.count(j)){ ss.erase(j); got -= ans[j]; } } depend[i + 1] = ss; sum[i + 1] = got; break; } if (depend[i].size() == 1){ ans[i] = sum[i]; depend[i].clear(); for (int j = 0; j < N; j++){ if (depend[j].count(i)){ sum[j] -= ans[i]; depend[j].erase(i); } } break; } if (depend[i].size()){ int x = sum[i] / (int)depend[i].size(); auto [vv, ll] = transaction(x); set <int> ss; for (auto x : vv) ss.insert(x), counter[x]++; int got = x - ll; for (int j = 0; j < N; j++){ if (ans[j] != -1 && ss.count(j)){ got -= ans[j]; ss.erase(j); } } assert(!ss.empty()); int k = *ss.begin(); depend[k] = ss; sum[k] = got; break; } } } for (int i = 0; i < N; i++){ while (counter[i] < i){ counter[i]++; transaction(ans[i]); } } }
#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...