Submission #365437

#TimeUsernameProblemLanguageResultExecution timeMemory
365437dynam1cZalmoxis (BOI18_zalmoxis)C++17
100 / 100
350 ms61716 KiB
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" #define all(c) (c).begin(),(c).end() // if you're reading this i hope to meet you in IOI 2021 // RECHECK CONSTRAINTS AFTER MAKING A REDUCTION signed main() { // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); std::ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<array<int, 3>> arr(n); for (int i = 0; i < n; i++) cin >> arr[i][0], arr[i][1] = i, arr[i][2] = i+1; auto oarr = arr; priority_queue<array<int, 2>> aug; for (int ii = 0; ii < 30; ii++) { vector<array<int, 3>> ar2; for (int i = 0; i < arr.size(); i++) { if (arr[i][0] == ii) { if (i < arr.size()-1 and arr[i+1][0] == ii) ar2.push_back({arr[i][0]+1, arr[i][1], arr[i+1][2]}), i++; else ar2.push_back({arr[i][0]+1, arr[i][1], arr[i][2]}), aug.push({arr[i][0], arr[i][2]}); } else ar2.push_back(arr[i]); } arr = ar2; } while (aug.size() < k) { auto [x, i] = aug.top(); aug.pop(); aug.push({x-1, i}); aug.push({x-1, i}); } vector<vector<int>> g(n+1); vector<int> res; while (!aug.empty()) { auto [x, i] = aug.top(); aug.pop(); g[i].push_back(x); } arr = oarr; for (int i = 0; i <= n; i++) { reverse(all(g[i])); for (int e : g[i]) res.push_back(e); if (i < n) res.push_back(arr[i][0]); } for (int e : res) cout << e << " "; cout << endl; } /* --- PSolving --- * Simplifying (getting rid of variables, conditions, code logic, etc.) * Reframing * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.) * Inducing * Divide and conquer * Working backwards * Visual intuition * !! Reductions don't have to be specializations, they can be generalizations */

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int i = 0; i < arr.size(); i++) {
      |                   ~~^~~~~~~~~~~~
zalmoxis.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if (i < arr.size()-1 and arr[i+1][0] == ii)
      |         ~~^~~~~~~~~~~~~~
zalmoxis.cpp:39:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |  while (aug.size() < k) {
      |         ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...