oj.uz

Submission #335453

# Submission time Handle Problem Language Result Execution time Memory
335453 2020-12-12T16:59:00 Z 3funnn Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 306 ms 15560 KB 
#include <bits/stdc++.h>
#define mp make_pair
 
using namespace std;
 
const int NMAX = 1000000;
int need;
 
void dfs(int val){
    if (need == 0 || val == 0){
        cout << val << " ";
        return;
    }
    --need;
    dfs(val - 1);
    dfs(val - 1);
}
 
int stk[NMAX + 5], top;
 
void Compress(){
    while (top >= 2 && stk[top] == stk[top - 1]){
        --top;
        ++stk[top];
    }
}
 
int main()
{
    int N, K;
    cin >> N >> K;
    vector <int> v(N);
    for (int i = 0;i < N;++i)
        cin >> v[i];
    need = K;
    vector <pair <int, bool>> a;
    stk[++top] = 31;
    for (int i = 0;i < N;++i){
        while (v[i] > stk[top]){
            --need;
            a.push_back(mp(stk[top], true));
            ++stk[top];
            Compress();
        }
        a.push_back(mp(v[i], false));
        stk[++top] = v[i];
        Compress();
    }
    while (stk[2] != 30){
        --need;
        a.push_back(mp(stk[top], true));
        ++stk[top];
        Compress();
    }
    for (int i = 0;i < a.size();++i){
        if (a[i].second == 0)
            cout << a[i].first << " ";
        else
            dfs(a[i].first);
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0;i < a.size();++i){
      |                    ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 15432 KB Output is correct
2 Correct 289 ms 15532 KB Output is correct
3 Correct 289 ms 15520 KB Output is correct
4 Correct 289 ms 15432 KB Output is correct
5 Correct 287 ms 15520 KB Output is correct
6 Correct 288 ms 15560 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 15432 KB Output is correct
2 Correct 306 ms 15480 KB Output is correct
3 Correct 295 ms 15560 KB Output is correct
4 Correct 302 ms 15508 KB Output is correct
5 Correct 292 ms 15560 KB Output is correct
6 Correct 296 ms 15504 KB Output is correct
7 Correct 292 ms 15504 KB Output is correct
8 Correct 294 ms 15552 KB Output is correct
9 Correct 258 ms 14188 KB Output is correct
10 Correct 168 ms 7652 KB Output is correct
11 Correct 209 ms 11644 KB Output is correct
12 Correct 110 ms 2284 KB Output is correct
13 Correct 112 ms 2368 KB Output is correct
14 Correct 110 ms 2340 KB Output is correct