oj.uz

Submission #255200

# Submission time Handle Problem Language Result Execution time Memory
255200 2020-07-31T14:11:12 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
30 / 100
 216 ms 16208 KB 
// M
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, k, A[N];
void Print(int a)
{
        if (k >= (1 << a) - 1)
        {
                for (int i = 0; i < (1 << a); i ++)
                        printf("0 ");
                return ;
        }
        while (a && k)
        {
                if ((1 << (a - 1)) <= k)
                {
                        for (int i = 0; i < (1 << (a - 1)); i ++)
                                printf("0 ");
                        k -= 1 << (a - 1);
                        a --;
                        continue;
                }
                printf("%d ", a - 1);
                k --; a --;
        }
        printf("%d ", 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);
        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

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:39: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:41: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 207 ms 16208 KB Output is correct
2 Correct 216 ms 16208 KB Output is correct
3 Correct 208 ms 16208 KB Output is correct
4 Correct 214 ms 16208 KB Output is correct
5 Correct 210 ms 15824 KB Output is correct
6 Correct 203 ms 15440 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 15440 KB not a zalsequence
2 Incorrect 197 ms 15568 KB Expected EOF
3 Incorrect 208 ms 15696 KB Expected EOF
4 Incorrect 207 ms 15440 KB not a zalsequence
5 Incorrect 195 ms 15440 KB not a zalsequence
6 Incorrect 200 ms 15440 KB not a zalsequence
7 Incorrect 201 ms 15568 KB not a zalsequence
8 Incorrect 198 ms 15568 KB not a zalsequence
9 Incorrect 185 ms 14288 KB Expected EOF
10 Incorrect 140 ms 10076 KB Expected EOF
11 Incorrect 169 ms 12120 KB Expected EOF
12 Incorrect 68 ms 4472 KB Expected EOF
13 Incorrect 74 ms 4472 KB Expected EOF
14 Incorrect 73 ms 4472 KB Expected EOF