Submission #335453

#	Time	Username	Problem	Language	Result	Execution time	Memory
335453		3funnn	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	306 ms	15560 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70