oj.uz

Submission #520191

# Submission time Handle Problem Language Result Execution time Memory
520191 2022-01-28T18:29:37 Z prvocislo Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 160 ms 20168 KB 
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <bitset>
#include <cmath>
#include <cassert>
typedef long long ll;
typedef long double ld;
using namespace std;

void compress(vector<int>& st)
{
    while (st.size() >= 2 && st[st.size() - 2] == st[st.size() - 1])
    {
        int x = st.back();
        st.pop_back();
        st.pop_back();
        st.push_back(x + 1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    vector<int> st, ans1, added;
    for (int i = 0; i < n; i++)
    {
        while (!st.empty() && st.back() < v[i])
        {
            st.push_back(st.back());
            ans1.push_back(st.back());
            added.push_back(1);
            compress(st);
        }
        st.push_back(v[i]);
        ans1.push_back(v[i]);
        added.push_back(0);
        compress(st);
    }
    while (st.size() > 1 || st.back() < 30)
    {
        st.push_back(st.back());
        ans1.push_back(st.back());
        added.push_back(1);
        compress(st);
    }
    assert(ans1.size() <= n + k);
    k = n + k - ans1.size();
    vector<int> ans2;
    for (int i = 0; i < ans1.size(); i++)
    {
        if (added[i])
        {
            int one = 0;
            vector<int> v = { ans1[i] };
            while (k && v.size())
            {
                while (v.back() == 1)
                {
                    v.pop_back();
                    one++;
                }
                if (v.empty()) break;
                int x = v.back();
                v.pop_back();
                v.push_back(x - 1);
                v.push_back(x - 1);
                k--;
            }
            for (int j : v) ans2.push_back(j);
            for (int j = 0; j < one; j++) ans2.push_back(1);
        }
        else
        {
            ans2.push_back(ans1[i]);
        }
    }
    for (int i = 0; i < ans2.size(); i++)
    {
        cout << ans2[i] << " \n"[i == ans2.size() - 1];
    }
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from zalmoxis.cpp:14:
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:59:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     assert(ans1.size() <= n + k);
      |            ~~~~~~~~~~~~^~~~~~~~
zalmoxis.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < ans1.size(); i++)
      |                     ~~^~~~~~~~~~~~~
zalmoxis.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0; i < ans2.size(); i++)
      |                     ~~^~~~~~~~~~~~~
zalmoxis.cpp:92:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         cout << ans2[i] << " \n"[i == ans2.size() - 1];
      |                                  ~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 18204 KB Output is correct
2 Correct 140 ms 18172 KB Output is correct
3 Correct 142 ms 18208 KB Output is correct
4 Correct 140 ms 18144 KB Output is correct
5 Correct 149 ms 18132 KB Output is correct
6 Correct 141 ms 18212 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 18148 KB Output is correct
2 Correct 143 ms 18732 KB Output is correct
3 Correct 140 ms 20168 KB Output is correct
4 Correct 139 ms 18136 KB Output is correct
5 Correct 138 ms 18140 KB Output is correct
6 Correct 143 ms 18144 KB Output is correct
7 Correct 160 ms 18164 KB Output is correct
8 Correct 141 ms 18220 KB Output is correct
9 Correct 134 ms 18460 KB Output is correct
10 Correct 105 ms 14476 KB Output is correct
11 Correct 116 ms 14752 KB Output is correct
12 Correct 86 ms 12256 KB Output is correct
13 Correct 93 ms 12228 KB Output is correct
14 Correct 72 ms 6324 KB Output is correct