Submission #255214

#	Time	Username	Problem	Language	Result	Execution time	Memory
255214		Kastanda	Zalmoxis (BOI18_zalmoxis)	C++11	100 / 100	236 ms	23120 KiB

zalmoxis

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, k, kk, A[N];
vector < int > Rs;
inline bool Check()
{
        vector < int > Stk;
        for (int i = 0; i < (int)Rs.size(); i ++)
        {
                int nw = Rs[i];
                if (Stk.size() && Stk.back() < nw)
                        return 0;
                while (Stk.size() && Stk.back() == nw)
                        Stk.pop_back(), nw ++;
                Stk.push_back(nw);
        }
        return (Stk.size() == 1 && Stk[0] == 30);
}
void Print(int a)
{
        if (k > (1 << a) - 1)
        {
                for (int i = 0; i < (1 << a); i ++)
                        Rs.push_back(0);
                k -= (1 << a) - 1;
                return ;
        }
        while (a && k)
        {
                if ((1 << (a - 1)) <= k)
                {
                        for (int i = 0; i < (1 << (a - 1)); i ++)
                                Rs.push_back(0);
                        k -= 1 << (a - 1);
                        a --;
                        continue;
                }
                Rs.push_back(a - 1);
                k --; a --;
        }
        Rs.push_back(a);
        return ;

        /*if (!k || !a)
                return void(printf("%d ", a));
        k --;
        Print(a - 1);
        Print(a - 1);
        return ;*/
}
int main()
{
        scanf("%d%d", &n, &k); kk = 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 ++;
                        Stk.push_back(nw);
                }
                R.push_back({A[i], 0});
        }
        R.pop_back(); n --;
        for (auto X : R)
        {
                if (!X.second)
                        Rs.push_back(X.first);
                else
                        Print(X.first);
        }
        assert((int)Rs.size() == n + kk);
        assert(Check());
        for (int a : Rs)
                printf("%d ", a);
        printf("\n");
        return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &k); kk = k;
         ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:57: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: 70 / 70