Submission #1251241

#TimeUsernameProblemLanguageResultExecution timeMemory
1251241aryan12선물 (IOI25_souvenirs)C++20
22 / 100
0 ms412 KiB
#include "souvenirs.h" #include <utility> #include <vector> #include <bits/stdc++.h> using namespace std; /* P[i + 2] * 2 <= P[i + 1] + P[i + 2] <= P[i] <= 2 * P[i + 1] So for a given value, P[i] (highest) cannot be < val / 3 */ void buy_souvenirs(int N, long long P0) { vector<int> cnt(N, 0); vector<long long> lowest_price_for_which_highest(N + 1, -1); lowest_price_for_which_highest[0] = P0; iota(cnt.begin(), cnt.end(), 0); long long cur_val = P0 - 1; std::pair<std::vector<int>, long long> res = transaction(cur_val); lowest_price_for_which_highest[1] = cur_val - res.second; for(int x: res.first) { cnt[x] -= 1; } bool omk = false, cntt = true; while(true) { int sum = accumulate(cnt.begin(), cnt.end(), 0LL); if(sum == 0) break; if(!cntt) { for(int i = N - 1; i >= 0; i--) { if(lowest_price_for_which_highest[i] == -1) { lowest_price_for_which_highest[i] = lowest_price_for_which_highest[i + 2] * 2; cur_val = lowest_price_for_which_highest[i]; omk = true; cntt = true; break; } } for(int i = 1; i < N; i++) { if(cnt[i] != 0) { cur_val = lowest_price_for_which_highest[i]; omk = true; cntt = true; break; } } } else if(res.first.size() == 1) { lowest_price_for_which_highest[res.first[0]] = cur_val - res.second; lowest_price_for_which_highest[res.first[0] + 1] = cur_val - res.second - 1; for(int i = N - 1; i >= 0; i--) { if(lowest_price_for_which_highest[i] == -1) { lowest_price_for_which_highest[i] = lowest_price_for_which_highest[i + 2] * 2; cur_val = lowest_price_for_which_highest[i]; omk = true; cntt = true; break; } } for(int i = 1; i < N; i++) { if(cnt[i] != 0) { cur_val = lowest_price_for_which_highest[i]; omk = true; cntt = true; break; } } } else if(res.first.size() >= 3) { cur_val = (cur_val - res.second) / 3; } else { cur_val = (cur_val - res.second) / 2; } if(!omk || cntt) { res = transaction(cur_val); for(int x: res.first) { cnt[x] -= 1; } lowest_price_for_which_highest[res.first[0]] = cur_val - res.second; if(omk) cntt = false; } } // std::pair<std::vector<int>, long long> res = transaction(3); return; }
#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...