Submission #1256543

#TimeUsernameProblemLanguageResultExecution timeMemory
1256543jamesbamberSouvenirs (IOI25_souvenirs)C++20
25 / 100
18 ms412 KiB
#include "souvenirs.h" #include <utility> #include <vector> #include <cassert> #include <iostream> using namespace std; void buy_souvenirs(int N, long long P0) { vector<long long> p(N, -1); vector<int> bought(N, 0); p[0] = P0; auto my_transaction = [&](long long M) { // cerr << "transaction: " << M << endl; auto [v, c] = transaction(M); for(int x: v) bought[x]++; return make_pair(v, M - c); }; auto clean_group = [&](vector<int> &v, long long &c) { vector<int> new_v; for(int x: v) { if(p[x] != -1) c -= p[x]; else new_v.push_back(x); } v = new_v; }; auto rec = [&](auto &&self, vector<int> v, long long c) -> void { cerr << v.size() << " " << c << endl; while(v.size() > 1) { auto [next_v, next_c] = my_transaction(c / v.size()); self(self, next_v, next_c); clean_group(v, c); } assert(v.size() == 1); p[v[0]] = c; }; for(int i=1; i<N; i++) { if(p[i] == -1) { auto [v, c] = my_transaction(p[i-1] - 1); rec(rec, v, c); } assert(p[i] != -1); // cerr << i << " price " << p[i] << endl; while(bought[i] < i) my_transaction(p[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...