제출 #1249747

#제출 시각아이디문제언어결과실행 시간메모리
1249747gelastropod선물 (IOI25_souvenirs)C++20
39 / 100
12 ms412 KiB
#include "souvenirs.h" #include <bits/stdc++.h> using namespace std; #define int long long void buy_souvenirs(signed N, long long P0) { vector<int> numbought(N, 0); vector<int> P(N, -1); P[0] = P0; vector<pair<vector<signed>, int>> vals; while (true) { bool done = true; int crnt = P0, ind = -1; for (int i = N - 1; i >= 0; i--) { if (P[i] == -1) { done = false; ind = i; } if (ind != -1 && P[i] != -1) break; } if (done) break; ind--; crnt = P[ind] - 1; while (true) { auto i = transaction(crnt); i.second = crnt - i.second; vector<signed> aaa; for (int j : i.first) { numbought[j]++; if (P[j] == -1) aaa.push_back(j); else i.second -= P[j]; } i.first = aaa; ind = i.first[0]; vals.push_back(i); for (int j : i.first) { i.second += j - i.first[0]; } crnt = (i.second - 1) / i.first.size(); if (i.first.size() == 1) break; } for (int i = 0; i < N; i++) { if (vals.empty()) break; auto iter = vals.end(); iter--; while (iter != vals.begin()) { vector<signed> aaa; for (int i : iter->first) { if (P[i] == -1) aaa.push_back(i); else iter->second -= P[i]; } iter->first = aaa; if (iter->first.size() == 1) { P[iter->first[0]] = iter->second; iter = vals.erase(iter); } iter--; } vector<signed> aaa; for (int i : iter->first) { if (P[i] == -1) aaa.push_back(i); else iter->second -= P[i]; } iter->first = aaa; if (iter->first.size() == 1) { P[iter->first[0]] = iter->second; vals.erase(iter); } } } for (int i = 0; i < N; i++) { for (int j = numbought[i]; j < i; j++) { transaction(P[i]); } } 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...