Submission #1249419

#TimeUsernameProblemLanguageResultExecution timeMemory
1249419mondellbitSouvenirs (IOI25_souvenirs)C++20
Compilation error
0 ms0 KiB
#include "souvenirs.h" #include <bits/stdc++.h> using namespace std; #define INF (long long)1e18 vector<long long> hidden_p; vector<int> counter; pair<vector<int>, long long> transaction(long long 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<long long> buy_souvenirs(int N, long long P0) { vector<set<int>> depend(N); vector<long long> sum(N); vector<long long> 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]++; long long 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()) { long long x = sum[i] / (int)depend[i].size(); auto [vv, ll] = transaction(x); set<int> ss; for (auto x : vv) ss.insert(x), counter[x]++; long long 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<long long> find_prices(int N) { hidden_p.resize(N); counter.assign(N, 0); // First find p0 long long low = 1, high = INF; long long p0 = -1; while (low <= high) { long long 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<long long> prices = buy_souvenirs(N, p0); hidden_p = prices; return prices; }

Compilation message (stderr)

souvenirs.cpp:22:19: error: ambiguating new declaration of 'std::vector<long long int> buy_souvenirs(int, long long int)'
   22 | vector<long long> buy_souvenirs(int N, long long P0) {
      |                   ^~~~~~~~~~~~~
In file included from souvenirs.cpp:1:
souvenirs.h:4:6: note: old declaration 'void buy_souvenirs(int, long long int)'
    4 | void buy_souvenirs(int N, long long P0);
      |      ^~~~~~~~~~~~~
souvenirs.cpp: In function 'std::vector<long long int> find_prices(int)':
souvenirs.cpp:132:45: error: conversion from 'void' to non-scalar type 'std::vector<long long int>' requested
  132 |     vector<long long> prices = buy_souvenirs(N, p0);
      |                                ~~~~~~~~~~~~~^~~~~~~