Submission #78939

#	Time	Username	Problem	Language	Result	Execution time	Memory
78939		bogdan10bos	Zalmoxis (BOI18_zalmoxis)	C++14	5 / 100	270 ms	32612 KiB

zalmoxis

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

int N, K, M;
int v[1000005];
vector<int> stv, add[1000005];

int printmore(int x, int need)
{
    if(x == 0)
    {
        printf("%d ", x);
        return 0;
    }

    if(need == 0)
    {
        printf("%d ", x);
        return 0;
    }

    if(need == 1)
    {
        printf("%d %d", x - 1, x - 1);
        return 1;
    }

    need--;
    int lft = need / 2;
    int rgt = need - lft;
    int tot = printmore(x - 1, lft) + printmore(x - 1, rgt) + 1;
    return tot;
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &K);
    for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
    v[N + 1] = 30;
    stv.push_back(v[1]);
    for(int i = 2; i <= N; i++)
    {
        while(stv.back() < v[i])
        {
            int val = stv.back();
            stv.pop_back();
            if(!stv.empty() && stv.back() == val)
            {
                stv.pop_back();
                stv.push_back(val + 1);
                continue;
            }

            add[i - 1].push_back(val); M++;
            stv.push_back(val + 1);
        }
        while((int)stv.size() > 1)
        {
            int x = stv.back();
            stv.pop_back();
            int y = stv.back();
            if(x == y)
            {
                stv.pop_back();
                stv.push_back(x + 1);
                continue;
            }
            stv.push_back(x);
            break;
        }
        stv.push_back(v[i]);
        while((int)stv.size() > 1)
        {
            int x = stv.back();
            stv.pop_back();
            int y = stv.back();
            if(x == y)
            {
                stv.pop_back();
                stv.push_back(x + 1);
                continue;
            }
            stv.push_back(x);
            break;
        }
    }

    assert(M <= K);
    int more = K - M;
    for(int i = 1; i <= N; i++)
    {
        printf("%d ", v[i]);
        for(auto x: add[i])
        {
            int pr = printmore(x, more);
            more -= pr;
        }
    }
    printf("\n");

    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:46:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
                                 ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 5 / 70