oj.uz

Submission #255209

# Submission time Handle Problem Language Result Execution time Memory
255209 2020-07-31T14:31:42 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
35 / 100
 226 ms 40784 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 ++;
                }
                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 224 ms 22224 KB Output is correct
2 Correct 224 ms 22224 KB Output is correct
3 Correct 224 ms 22224 KB Output is correct
4 Correct 225 ms 22224 KB Output is correct
5 Correct 226 ms 22224 KB Output is correct
6 Correct 216 ms 22096 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 165 ms 40656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 162 ms 40780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 152 ms 32976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 156 ms 40784 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 152 ms 40580 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 161 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 156 ms 40532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 141 ms 38268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 59 ms 17892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 95 ms 31184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 17 ms 8684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 13 ms 8684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 90 ms 6364 KB Output is correct