Submission #249425

#	Time	Username	Problem	Language	Result	Execution time	Memory
249425		thebes	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	288 ms	47864 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

const int MN = 1e6+6, MM = 30;
int N, K, i, j, cur, id, nxt, arr[MN], ds[MN], val[MN];
pair<int,int> b[MN]; vector<int> add[MN];

int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);}
void expand(int x){
    if(K>0&&x>0) K--, expand(x-1), expand(x-1);
    else printf("%d ",x);
}

int main(){
    scanf("%d%d",&N,&K);
    for(i=1;i<=N;i++){
        scanf("%d",&arr[i]);
        b[i] = {i, i};
        ds[i] = i;
        val[i] = arr[i];
    }
    for(j=0;j<MM;j++){
        cur = 0;
        while(cur<N){
            id = fnd(cur+1);
            if(val[id]==j){
                nxt = fnd(b[id].second+1);
                if(b[id].second<N&&val[nxt]==j){
                    ds[nxt] = id;
                    b[id].second = b[nxt].second;
                }
                else{
                    add[b[id].second].push_back(j); K--;
                }
                val[id]++;
            }
            cur = b[id].second;
        }
    }
    for(i=1;i<=N;i++){
        printf("%d ",arr[i]);
        for(auto v : add[i])
            expand(v);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:15: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:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~

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