oj.uz

Submission #209854

# Submission time Handle Problem Language Result Execution time Memory
209854 2020-03-15T17:49:04 Z nicolaalexandra Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 346 ms 39800 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 329 ms 37624 KB Output is correct
2 Correct 328 ms 37624 KB Output is correct
3 Correct 331 ms 37624 KB Output is correct
4 Correct 331 ms 37624 KB Output is correct
5 Correct 337 ms 37624 KB Output is correct
6 Correct 345 ms 37624 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 37628 KB Output is correct
2 Correct 340 ms 37624 KB Output is correct
3 Correct 334 ms 37752 KB Output is correct
4 Correct 343 ms 37624 KB Output is correct
5 Correct 329 ms 37624 KB Output is correct
6 Correct 334 ms 37624 KB Output is correct
7 Correct 339 ms 37624 KB Output is correct
8 Correct 338 ms 37624 KB Output is correct
9 Correct 310 ms 39800 KB Output is correct
10 Correct 194 ms 34160 KB Output is correct
11 Correct 236 ms 37108 KB Output is correct
12 Correct 110 ms 27876 KB Output is correct
13 Correct 110 ms 27876 KB Output is correct
14 Correct 118 ms 27876 KB Output is correct