oj.uz

Submission #255206

# Submission time Handle Problem Language Result Execution time Memory
255206 2020-07-31T14:26:44 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
30 / 100
 239 ms 40912 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 --;
        for (auto X : R)
        {
                if (!X.second)
                        Rs.push_back(X.first);
                else
                        Print(X.first);
        }
        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 223 ms 22240 KB Output is correct
2 Correct 239 ms 22352 KB Output is correct
3 Correct 222 ms 22224 KB Output is correct
4 Correct 225 ms 22236 KB Output is correct
5 Correct 231 ms 22388 KB Output is correct
6 Correct 223 ms 22224 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 157 ms 40912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 151 ms 32976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 163 ms 40656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 155 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 157 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 166 ms 40656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 173 ms 40584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 134 ms 38480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 79 ms 28244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 102 ms 31184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 24 ms 16992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 26 ms 17000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 183 ms 12624 KB Expected EOF