Submission #1256642

#TimeUsernameProblemLanguageResultExecution timeMemory
1256642pandaa73Souvenirs (IOI25_souvenirs)C++20
0 / 100
2 ms412 KiB
#include <bits/stdc++.h> using namespace std; #define lf "\n" #define ff endl #define _ << ' ' << #define all(x) begin(x),end(x) #define rall(x) rbegin(x),rend(x) #define infos(str) do { fprintf(stderr, str"\n"); } while(0) #define infor(str, ...) do { fprintf(stderr, str, __VA_ARGS__); } while(0) #define infof(str, ...) do { fprintf(stderr, str"\n", __VA_ARGS__); } while(0) #ifndef DEBUG #undef infos #undef infor #undef infof #define infos(str) #define infor(str, ...) #define infof(str, ...) #endif using ll = long long; constexpr int LOG = 20; constexpr int MOD = 1e9+7; constexpr int MAXN = 1e5+7; std::pair<std::vector<int>, long long> transaction(long long M); void buy_souvenirs(int N, long long P0) { vector<ll> p(N); p[0] = P0; for(int i = 1; i < N; ++i) p[i] = (p[i - 1] + 1) / 2; vector<int> cnt(N); infos("min values of p:"); for(auto x: p) infor("%d ", x); infos(""); infos(""); ll mn = 0; for(int i = 1; i < N - 1; ++i) mn += p[i]; ll ask = max(1LL, P0 - 1 - mn); infos(""); while(1) { auto [q, r] = transaction(ask); if(q.size() == 1 && q[0] == N - 1) { p[N - 1] = ask - r; break; } for(auto x: q) { cnt[x]++; if(x < N - 1) ask -= p[x]; } } infof("p[%d] is %lld", N - 1, p[N - 1]); for(int i = N - 2; i > 0; i--) { if(cnt[i] >= i) continue; ll pay = 2 * p[i + 1]; auto [q, r] = transaction(pay); for(auto x: q) { cnt[x]++; if(x > i) pay -= p[x]; } pay -= r; p[i] = pay; infof("p[%d] is %lld", i, pay); } for(int i = 1; i < N; ++i) { for(int j = 0; j < i - cnt[i]; ++j) 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...