oj.uz

Submission #255188

# Submission time Handle Problem Language Result Execution time Memory
255188 2020-07-31T13:57:51 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
35 / 100
 1000 ms 31312 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 221 ms 16336 KB Output is correct
2 Correct 213 ms 16312 KB Output is correct
3 Correct 210 ms 16456 KB Output is correct
4 Correct 219 ms 16336 KB Output is correct
5 Correct 212 ms 16444 KB Output is correct
6 Correct 211 ms 16336 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 16336 KB not a zalsequence
2 Execution timed out 1080 ms 31312 KB Time limit exceeded
3 Execution timed out 1079 ms 31048 KB Time limit exceeded
4 Incorrect 228 ms 16336 KB not a zalsequence
5 Incorrect 243 ms 16336 KB not a zalsequence
6 Incorrect 254 ms 16368 KB not a zalsequence
7 Incorrect 225 ms 16340 KB not a zalsequence
8 Incorrect 227 ms 16336 KB not a zalsequence
9 Incorrect 214 ms 14704 KB not a zalsequence
10 Incorrect 152 ms 7644 KB not a zalsequence
11 Incorrect 164 ms 11748 KB not a zalsequence
12 Incorrect 108 ms 2424 KB not a zalsequence
13 Incorrect 100 ms 2296 KB not a zalsequence
14 Correct 102 ms 2376 KB Output is correct