Submission #1249398

#TimeUsernameProblemLanguageResultExecution timeMemory
1249398mondellbitSouvenirs (IOI25_souvenirs)C++20
Compilation error
0 ms0 KiB
#include "souvenirs.h" #include <bits/stdc++.h> using namespace std; vector<int> hidden_p; vector<int> counter; pair<vector<int>, int> transaction(int m) { vector<int> bought; for (int i = 0; i < hidden_p.size(); i++) { if (m >= hidden_p[i]) { m -= hidden_p[i]; bought.push_back(i); counter[i]++; } } return make_pair(bought, m); } vector<int> buy_souvenirs(int n, int p0) { vector<set<int>> depend(n); vector<int> sum(n); vector<int> ans(n, -1); ans[0] = p0; counter.assign(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]); } } return ans; } vector<int> find_prices(int N) { hidden_p.resize(N); counter.assign(N, 0); // First find p0 int low = 1, high = INF; int p0 = -1; while (low <= high) { int mid = (low + high) / 2; auto [bought, rem] = transaction(mid); if (bought.size() == 1 && bought[0] == 0) { p0 = mid; break; } else if (bought.size() > 0 && bought[0] == 0) { high = mid - 1; } else { low = mid + 1; } } // Now use the buy_souvenirs function vector<int> prices = buy_souvenirs(N, p0); return prices; }

Compilation message (stderr)

souvenirs.cpp: In function 'std::vector<int> find_prices(int)':
souvenirs.cpp:110:25: error: 'INF' was not declared in this scope
  110 |     int low = 1, high = INF;
      |                         ^~~