oj.uz

Submission #255214

# Submission time Handle Problem Language Result Execution time Memory
255214 2020-07-31T14:41:12 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 236 ms 23120 KB 
// 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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 22652 KB Output is correct
2 Correct 225 ms 22852 KB Output is correct
3 Correct 215 ms 22736 KB Output is correct
4 Correct 224 ms 22864 KB Output is correct
5 Correct 228 ms 23120 KB Output is correct
6 Correct 223 ms 22864 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 23120 KB Output is correct
2 Correct 231 ms 22992 KB Output is correct
3 Correct 223 ms 22992 KB Output is correct
4 Correct 216 ms 22992 KB Output is correct
5 Correct 232 ms 23024 KB Output is correct
6 Correct 220 ms 22944 KB Output is correct
7 Correct 226 ms 23024 KB Output is correct
8 Correct 235 ms 23024 KB Output is correct
9 Correct 205 ms 21712 KB Output is correct
10 Correct 140 ms 11620 KB Output is correct
11 Correct 162 ms 18256 KB Output is correct
12 Correct 88 ms 6364 KB Output is correct
13 Correct 100 ms 6364 KB Output is correct
14 Correct 90 ms 6364 KB Output is correct