oj.uz

Submission #61182

# Submission time Handle Problem Language Result Execution time Memory
61182 2018-07-25T10:07:33 Z SpaimaCarpatilor Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 359 ms 11592 KB 
#include<bits/stdc++.h>

using namespace std;

int N, K, M, nr, ans[1000009], a[1000009], stk[1000009];
bool type[1000009];

void print (int val, int &needToAdd)
{
    if (needToAdd == 0 || val == 0)
    {
        printf ("%d ", val);
        return ;
    }
    needToAdd --;
    print (val - 1, needToAdd);
    print (val - 1, needToAdd);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &K);
for (int i=1; i<=N; i++)
    scanf ("%d", &a[i]);
ans[1] = a[1], type[1] = 1;
stk[1] = a[1], nr = 1, M = 1;
for (int i=2; i<=N; i++)
{
    while (a[i] > stk[nr])
    {
        ans[++M] = stk[nr];
        stk[nr + 1] = stk[nr], nr ++;
        while (nr >= 2 && stk[nr] == stk[nr - 1])
            nr --, stk[nr] ++;
    }
    if (a[i] <= stk[nr])
    {
        ans[++M] = a[i], type[M] = 1;
        if (a[i] < stk[nr]) stk[++nr] = a[i];
        else
        {
            stk[++nr] = a[i];
            while (nr >= 2 && stk[nr] == stk[nr - 1])
                nr --, stk[nr] ++;
        }
        continue;
    }
}
while (nr > 1 || stk[1] < 30)
{
    ans[++M] = stk[nr];
    stk[nr + 1] = stk[nr], nr ++;
    while (nr >= 2 && stk[nr] == stk[nr - 1])
        nr --, stk[nr] ++;
}
int needToAdd = K - (M - N);
for (int i=1; i<=M; i++)
    if (type[i] == 1) printf ("%d ", ans[i]);
    else
    if (type[i] == 0) print (ans[i], needToAdd);
printf ("\n");
return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d", &N, &K);
 ~~~~~~^~~~~~~~~~~~~~~~~
zalmoxis.cpp:27:11: 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 238 ms 11384 KB Output is correct
2 Correct 232 ms 11436 KB Output is correct
3 Correct 359 ms 11436 KB Output is correct
4 Correct 263 ms 11436 KB Output is correct
5 Correct 231 ms 11436 KB Output is correct
6 Correct 221 ms 11436 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 11464 KB Output is correct
2 Correct 294 ms 11464 KB Output is correct
3 Correct 342 ms 11592 KB Output is correct
4 Correct 239 ms 11592 KB Output is correct
5 Correct 269 ms 11592 KB Output is correct
6 Correct 232 ms 11592 KB Output is correct
7 Correct 272 ms 11592 KB Output is correct
8 Correct 247 ms 11592 KB Output is correct
9 Correct 226 ms 11592 KB Output is correct
10 Correct 139 ms 11592 KB Output is correct
11 Correct 161 ms 11592 KB Output is correct
12 Correct 164 ms 11592 KB Output is correct
13 Correct 98 ms 11592 KB Output is correct
14 Correct 128 ms 11592 KB Output is correct