oj.uz

Submission #255205

# Submission time Handle Problem Language Result Execution time Memory
255205 2020-07-31T14:25:57 Z Kastanda Zalmoxis (BOI18_zalmoxis) C++11
30 / 100
 235 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);
                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: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 226 ms 22168 KB Output is correct
2 Correct 228 ms 22184 KB Output is correct
3 Correct 220 ms 22140 KB Output is correct
4 Correct 225 ms 22352 KB Output is correct
5 Correct 235 ms 22224 KB Output is correct
6 Correct 224 ms 22096 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 148 ms 40784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 154 ms 32976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 149 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 148 ms 40656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 154 ms 40532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 159 ms 40528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 155 ms 40488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 140 ms 38300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 78 ms 28232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 120 ms 31208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 25 ms 16988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 25 ms 17000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 26 ms 16992 KB Execution killed with signal 11 (could be triggered by violating memory limits)