oj.uz

Submission #255207

# Submission time Handle Problem Language Result Execution time Memory
255207 2020-07-31T14:27:51 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
30 / 100
 252 ms 24656 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);
                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 ++;
                }
                R.push_back({A[i], 0});
        }
        R.pop_back(); n --;
  		assert(k >= 0);
        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:54: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:56: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 208 ms 22224 KB Output is correct
2 Correct 211 ms 22352 KB Output is correct
3 Correct 207 ms 22224 KB Output is correct
4 Correct 223 ms 22260 KB Output is correct
5 Correct 219 ms 22228 KB Output is correct
6 Correct 206 ms 22096 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 22224 KB not a zalsequence
2 Runtime error 139 ms 24656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 142 ms 24528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 207 ms 22224 KB not a zalsequence
5 Incorrect 215 ms 22224 KB not a zalsequence
6 Incorrect 213 ms 22224 KB not a zalsequence
7 Incorrect 204 ms 22240 KB not a zalsequence
8 Incorrect 213 ms 22352 KB not a zalsequence
9 Incorrect 194 ms 21200 KB Expected EOF
10 Incorrect 252 ms 21468 KB Expected EOF
11 Incorrect 243 ms 19808 KB Expected EOF
12 Incorrect 172 ms 12752 KB Expected EOF
13 Incorrect 171 ms 12624 KB Expected EOF
14 Incorrect 162 ms 12692 KB Expected EOF