oj.uz

Submission #712103

# Submission time Handle Problem Language Result Execution time Memory
712103 2023-03-18T06:37:01 Z wenqi Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 173 ms 8408 KB 
// trans rights
#include <bits/extc++.h>
using namespace std;
using ll = long long;

int N, K;

int inp[1000069];

stack<int> f;
vector<pair<int, int>> probes;

void probe(int x)
{
    while (f.size() and x == f.top())
    {
        f.pop();
        x++;
    }
    f.push(x);
}

void curse(int x, int &u)
{
    if (x and u)
    {
        u--;
        curse(x - 1, u);
        curse(x - 1, u);
    }else{
        cout << x << ' ';
    }
}

int main(int argc, const char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i <= N; i++)
    {
        int x = 30;
        if (i < N)
            cin >> x;
        inp[i] = x;
        while (f.size() and x > f.top())
        {
            probes.emplace_back(f.top(), i);
            probe(f.top());
        }
        if (i < N)
            probe(x);
    }
    int lo = K - probes.size();
    int ptr = 0;
    for (int i = 0; i <= N; i++)
    {
        while (ptr < probes.size() and probes[ptr].second <= i)
        {
            curse(probes[ptr].first, lo);
            ptr++;
        }
        if (i < N)
            cout << inp[i] << ' ';
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main(int, const char**)':
zalmoxis.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while (ptr < probes.size() and probes[ptr].second <= i)
      |                ~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 8276 KB Output is correct
2 Correct 138 ms 8316 KB Output is correct
3 Correct 141 ms 8304 KB Output is correct
4 Correct 141 ms 8304 KB Output is correct
5 Correct 153 ms 8380 KB Output is correct
6 Correct 145 ms 8296 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 8328 KB Output is correct
2 Correct 139 ms 8316 KB Output is correct
3 Correct 153 ms 8304 KB Output is correct
4 Correct 138 ms 8308 KB Output is correct
5 Correct 148 ms 8324 KB Output is correct
6 Correct 173 ms 8380 KB Output is correct
7 Correct 148 ms 8408 KB Output is correct
8 Correct 151 ms 8348 KB Output is correct
9 Correct 156 ms 8308 KB Output is correct
10 Correct 109 ms 5292 KB Output is correct
11 Correct 125 ms 6636 KB Output is correct
12 Correct 83 ms 2252 KB Output is correct
13 Correct 80 ms 2224 KB Output is correct
14 Correct 86 ms 2292 KB Output is correct