oj.uz

Submission #78940

# Submission time Handle Problem Language Result Execution time Memory
78940 2018-10-09T16:42:24 Z bogdan10bos Zalmoxis (BOI18_zalmoxis) C++14
10 / 100
 259 ms 32684 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 29816 KB Unexpected end of file - int32 expected
2 Incorrect 231 ms 29836 KB Unexpected end of file - int32 expected
3 Incorrect 222 ms 30048 KB Unexpected end of file - int32 expected
4 Incorrect 227 ms 30048 KB Unexpected end of file - int32 expected
5 Incorrect 240 ms 30048 KB Unexpected end of file - int32 expected
6 Incorrect 220 ms 30048 KB Unexpected end of file - int32 expected

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 30048 KB not a zalsequence
2 Correct 217 ms 30048 KB Output is correct
3 Correct 226 ms 30072 KB Output is correct
4 Incorrect 219 ms 30072 KB not a zalsequence
5 Incorrect 231 ms 30096 KB not a zalsequence
6 Incorrect 225 ms 30096 KB not a zalsequence
7 Incorrect 225 ms 30188 KB not a zalsequence
8 Incorrect 220 ms 30224 KB not a zalsequence
9 Incorrect 259 ms 32684 KB not a zalsequence
10 Incorrect 176 ms 32684 KB not a zalsequence
11 Incorrect 213 ms 32684 KB not a zalsequence
12 Incorrect 30 ms 32684 KB Unexpected end of file - int32 expected
13 Incorrect 23 ms 32684 KB Unexpected end of file - int32 expected
14 Incorrect 23 ms 32684 KB Unexpected end of file - int32 expected