Submission #255188

#	Time	Username	Problem	Language	Result	Execution time	Memory
255188		Kastanda	Zalmoxis (BOI18_zalmoxis)	C++11	35 / 100	1080 ms	31312 KiB

zalmoxis

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, k, A[N];
void Print(int a)
{
        if (!k || !a)
                return void(printf("%d ", a));
        k --;
        Print(a - 1);
        Print(a - 1);
        return ;
}
int main()
{
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i ++)
                scanf("%d", &A[i]);
        vector < pair < int , int > > R;
        vector < int > Stk;
        Stk.push_back(A[1]);
        R.push_back({A[1], 0});
        A[++ n] = 30;
        for (int i = 2; i <= n; i ++)
        {
                int nw = A[i];
                while (Stk.size() && Stk.back() == nw)
                        Stk.pop_back(), nw ++;
                if (!Stk.size() || Stk.back() > nw)
                        Stk.push_back(nw);
                else
                {
                        assert(nw == A[i]);
                        R.push_back({Stk.back(), 1}), k --;
                        while (Stk.size() && Stk.back() < nw)
                        {
                                int a = Stk.back(), c = 0;
                                Stk.pop_back();
                                int trg = Stk.size() ? Stk.back() : 30;
                                trg = min(trg, nw);
                                while (a < trg)
                                {
                                        if (c)
                                                R.push_back({a, 1}), k --;
                                        a ++; c ++;
                                }
                        }
                        while (Stk.size() && Stk.back() == nw)
                                Stk.pop_back(), nw ++;
                        Stk.push_back(nw);
                        nw = A[i];
                        while (Stk.size() && Stk.back() == nw)
                                Stk.pop_back(), nw ++;
                }
                R.push_back({A[i], 0});
        }
        R.pop_back();
        for (auto X : R)
        {
                if (!X.second)
                        printf("%d ", X.first);
                else
                        Print(X.first);
        }
        printf("\n");
        return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &k);
         ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:19:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &A[i]);
                 ~~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 5 / 70