제출 #1251252

#제출 시각아이디문제언어결과실행 시간메모리
1251252aryan12선물 (IOI25_souvenirs)C++20
22 / 100
13 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); // cout << "omk = " << omk << ", cntt = " << cntt << endl; if(sum == 0) break; if(!cntt) { for(int i = N - 1; i >= 0; i--) { if(lowest_price_for_which_highest[i] == -1) { // cout << "coming here for i = " << i << endl; lowest_price_for_which_highest[i] = lowest_price_for_which_highest[i + 1] * 2; cur_val = lowest_price_for_which_highest[i]; omk = true; cntt = true; break; } } if(!omk || !cntt) { for(int i = 1; i < N; i++) { if(cnt[i] != 0) { // cout << "i = " << i << ", cnt[i] = " << cnt[i] << endl; 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) { // cout << "coming here for i = " << i << ", and 2" << endl; lowest_price_for_which_highest[i] = lowest_price_for_which_highest[i + 1] * 2; cur_val = lowest_price_for_which_highest[i]; omk = true; cntt = true; break; } } if(!omk || !cntt) { for(int i = 1; i < N; i++) { if(cnt[i] != 0) { // cout << "i = " << i << ", cnt[i] = " << cnt[i] << endl; 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; } long long ok = res.first.size(); lowest_price_for_which_highest[res.first[0]] = cur_val - res.second - (ok * (ok - 1)) / 2; 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...