oj.uz

Submission #1089871

# Submission time Handle Problem Language Result Execution time Memory
1089871 2024-09-17T10:38:37 Z lucri Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 262 ms 50656 KB 
#include <bits/stdc++.h>
using namespace std;
int n,k,v[1000010];
vector<int>ad[1000010];
vector<pair<int,int>>val[35];
void scrie(int val)
{
    if(val==0||k==0)
    {
        cout<<val<<' ';
        return;
    }
    --k;
    scrie(val-1);
    scrie(val-1);
    return;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
        val[v[i]].push_back({i,i});
    }
    for(int va=0;va<=29;++va)
    {
        sort(val[va].begin(),val[va].end());
        int sz=val[va].size();
        for(int i=0;i<sz;++i)
        {
            if(i+1==sz||val[va][i].second+1!=val[va][i+1].first)
            {
                --k;
                ad[val[va][i].second].push_back(va);
                val[va+1].push_back(val[va][i]);
            }
            else
            {
                val[va+1].push_back({val[va][i].first,val[va][i+1].second});
                ++i;
            }
        }
        val[va].clear();
    }
    if(k<0)
        return -1;
    if(val[30].size()!=1)
        return -1;
    if(val[30][0].first!=1||val[30][0].second!=n)
        return -1;
    for(int i=1;i<=n;++i)
    {
        cout<<v[i]<<' ';
        for(auto x:ad[i])
            scrie(x);
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 48404 KB Output is correct
2 Correct 262 ms 48452 KB Output is correct
3 Correct 246 ms 48444 KB Output is correct
4 Correct 245 ms 48584 KB Output is correct
5 Correct 254 ms 48728 KB Output is correct
6 Correct 251 ms 48988 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 48044 KB Output is correct
2 Correct 242 ms 49528 KB Output is correct
3 Correct 250 ms 48196 KB Output is correct
4 Correct 240 ms 48820 KB Output is correct
5 Correct 234 ms 49116 KB Output is correct
6 Correct 245 ms 50656 KB Output is correct
7 Correct 248 ms 48832 KB Output is correct
8 Correct 250 ms 48736 KB Output is correct
9 Correct 217 ms 48620 KB Output is correct
10 Correct 132 ms 36176 KB Output is correct
11 Correct 172 ms 41736 KB Output is correct
12 Correct 65 ms 25680 KB Output is correct
13 Correct 61 ms 25848 KB Output is correct
14 Correct 64 ms 25680 KB Output is correct