제출 #1256633

#제출 시각아이디문제언어결과실행 시간메모리
1256633pandaa73선물 (IOI25_souvenirs)C++20
4 / 100
0 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] = max(1LL, (p[i - 1] + 1) / 2); vector<int> cnt(N); ll mn = 0; for(int i = 1; i < N - 1; ++i) mn += p[i]; ll ask = P0 - 1 - mn; 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]; } } 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[i]; } pay -= r; p[i] = pay; for(int i = 0; i < i - cnt[i]; ++i) transaction(pay); } }
#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...