Submission #209854

#	Time	Username	Problem	Language	Result	Execution time	Memory
209854		nicolaalexandra	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	346 ms	39800 KiB

zalmoxis

#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;
int v[DIM];
vector <int> L[DIM],w;
pair <int,int> sol[DIM];
int n,i,j,poz,k,sol_poz,idx,el;

int solve (int val){

    if (v[idx] == val){ /// am deja valoarea pe care o caut
        idx++;
        return idx;
    }

    if (!val)
        return 0;

    /// stanga

    int poz = solve (val-1);

    if (poz > n || v[poz] > val-1){
        /// sunt obligata sa pun aici val
        L[poz-1].push_back(val-1);
        k--;
        /*sol = val-1;
        sol_poz = poz-1;*/

        return poz;
    }

    /// dreapta
    return solve (val-1);
}
void descompune (int val){
    if (val <= 1 || !k){
        w.push_back(val);
        return;
    }

    /// val -> val-1, val-1
    k--;

    descompune(val-1);
    descompune(val-1);
}

int main (){

  //  ifstream cin ("zalmoxis.in");
  //  ofstream cout ("zalmoxis.out");

    cin>>n>>k;
    for (i=1;i<=n;i++)
        cin>>v[i];

    idx = 1;
    solve (30);

    for (i=1;i<=n;i++){
        sol[++el] = make_pair(v[i],0);
        //cout<<v[i]<<" ";
        for (int j=0;j<L[i].size();j++)
            sol[++el] = make_pair(L[i][j],1);

    }
    for (i=1;i<=el;i++){
        if (!k){
            cout<<sol[i].first<<" ";
            continue;
        }

        if (!sol[i].second)
            cout<<sol[i].first<<" ";
        else {
            /// inseamna ca pot sa il mai descompun

            int x = sol[i].first;
            w.clear();
            descompune (sol[i].first);
            for (auto it : w)
                cout<<it<<" ";
            /*if (x < k){
                k -= x;
                cout<<1<<" ";
                for (j=1;j<=x-1;j++)
                    cout<<j<<" ";
            } else {
                cout<<x-k<<" ";
                for (j=x-k;j<x;j++)
                    cout<<j<<" ";
            }*/
        }
    }


    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0;j<L[i].size();j++)
                      ~^~~~~~~~~~~~
zalmoxis.cpp:79:17: warning: unused variable 'x' [-Wunused-variable]
             int x = sol[i].first;
                 ^

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