Submission #1253762

#TimeUsernameProblemLanguageResultExecution timeMemory
1253762t_hollSouvenirs (IOI25_souvenirs)C++20
39 / 100
12 ms424 KiB
#include <bits/stdc++.h> #include "souvenirs.h" #define MULTITEST false using namespace std; vector<bool> solved; vector<long long> values; int N; struct Pivot { long long sum = 0; vector<int> indices; long long remainder () { long long nsum = sum; int ncount = indices.size(); for (int i : indices) { if (solved[i]) { ncount --; nsum += values[i]; } } return nsum / ncount; } pair<int, long long> pivot_property () { long long value = sum; int index = indices[0]; for (int i : indices) { value -= values[i]; } return { index, value }; } bool pivot_solved () { int scount = 1; for (int i : indices) { if (solved[i]) { scount ++; } } return scount == indices.size(); } }; vector<int> built_count; Pivot create_pivot (long long M) { const auto res = transaction(M); Pivot p; p.sum = M - res.second; p.indices = res.first; for (int i : p.indices) built_count[i] ++; return p; } void buy_souvenirs (int _N, long long _P0) { N = _N; values.resize(N); solved.resize(N); built_count.resize(N); solved[0] = true; values[0] = _P0; vector<Pivot> pivots; pivots.push_back({ -1, { 0 } }); while (pivots.size() != 0) { Pivot &p = pivots.back(); if (p.sum != -1 && p.pivot_solved()) { pair<int, long long> res = p.pivot_property(); int p_id = res.first; long long p_vl = res.second; solved[p_id] = true; values[p_id] = p_vl; pivots.pop_back(); continue ; } int ppos = p.indices[0]; bool found_better = false; for (int j = N - 2; j >= ppos; j --) { if (solved[j] && !solved[j + 1]) { pivots.push_back(create_pivot(values[j] - 1)); found_better = true; break ; } } if (found_better) continue ; if (p.sum == -1) break ; pivots.push_back(create_pivot(p.remainder())); } for (int i = 0; i < N; i ++) { while (built_count[i] < i) { built_count[i] ++; transaction(values[i]); } } }
#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...