Submission #61182

#	Time	Username	Problem	Language	Result	Execution time	Memory
61182		SpaimaCarpatilor	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	359 ms	11592 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70