제출 #1251622

#제출 시각아이디문제언어결과실행 시간메모리
1251622fafnir선물 (IOI25_souvenirs)C++20
25 / 100
12 ms412 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "souvenirs.h" #endif using namespace std; #ifdef LOCAL vector<long long> vals; vector<int> bought; std::pair<std::vector<int>, long long> transaction(long long M) { vector<int> res; const int n = vals.size(); for (int i = 0; i < n; ++i) { if (vals[i] <= M) { res.push_back(i); M -= vals[i]; bought[i]++; } } return make_pair(res,M); } #endif /* p[0] > p[1] > ... > p[n-1] ST 1: *) p[0] > p[1] *) Make transaction p[0]-1 -> Then buying exactly one of type 1 ST 4: *) p[0] > p[1] > p[2] *) T1: M=p[0]-1 --> Case 1: Buying only one souvenir - Bought p[1] - C := M-p[1] <--> p[1] = M-C - T2: p[1]-1 --> Case 2: Bought 2 souvenirs M=100, C=11 (M-C)/2 - 1 100 coins, get back 11 -> 2 souvenirs are 89 - p[1] > p[2] - p[1] + p[2] = 89 - 89 > 2*p[2] - 44 > p[2] p[2] <= 43 */ void buy_souvenirs(int N, long long P0) { if (N == 2) { transaction(P0-1); } else if (N == 3) { long long M = P0-1; auto r = transaction(M); long long C = r.second; if (r.first.size() == 1) { transaction(M-C-1); transaction(M-C-1); } else { if ((M-C) % 2 == 0) { transaction((M-C)/2-1); } else { transaction((M-C)/2); } } } else { // Subtask 2 for (int j = 1; j <= N-1; ++j) { for (int i = j; i <= N-1; ++i) { transaction(N-i); } } } } #ifdef LOCAL int32_t main() { int tc; cin >> tc; while (tc--) { int n; cin >> n; bought.resize(n); vals.resize(n); for (auto& e : vals) cin >> e; fill_n(bought.begin(), n, 0); buy_souvenirs(n, vals[0]); for (int i = 0; i < 3; ++i) { cout << bought[i] << ' '; } cout << '\n'; } return 0; } #endif
#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...