oj.uz

Submission #647984

# Submission time Handle Problem Language Result Execution time Memory
647984 2022-10-04T17:42:24 Z toma_ariciu Zalmoxis (BOI18_zalmoxis) C++17
40 / 100
 245 ms 22244 KB 
/// Preset de orice altceva
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>

using namespace std;

int n, k, v[1000005], ind, diff;
vector <pair<int, bool>> sol;
vector <int> ans;

void dfs(int val)
{
    if(val == -1)
        return;
    if(v[ind] == val)
    {
        ind++;
        sol.push_back({val, 1});
        return;
    }
    if(v[ind] < val)
    {
        dfs(val - 1);
        dfs(val - 1);
    }
    else
        sol.push_back({val, 0});
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    v[n + 1] = 31;
    ind = 1;
    dfs(30);
    diff = n + k - sol.size();
    for(auto elem : sol)
    {
        if(elem.second == 1)
            ans.push_back(elem.first);
        else if(diff != 0)
        {
            diff++;
            if((1 << elem.first) >= diff)
            {
                for(int i = 0; i <= elem.first; i++)
                {
                    if(!((1 << i) & diff))
                        continue;
                    for(int j = 0; j < (1 << i); j++)
                        ans.push_back(elem.first - i - 1);
                }
                diff = 0;
            }
            else
            {
                diff -= (1 << elem.first);
                for(int i = 0; i < (1 << elem.first); i++)
                    ans.push_back(0);
            }
        }
        else
            ans.push_back(elem.first);
    }
    for(int elem : ans)
        cout << elem << ' ';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 22192 KB Output is correct
2 Correct 245 ms 22104 KB Output is correct
3 Correct 229 ms 22148 KB Output is correct
4 Correct 232 ms 22132 KB Output is correct
5 Correct 229 ms 22116 KB Output is correct
6 Correct 227 ms 22140 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 22044 KB not a zalsequence
2 Correct 233 ms 22244 KB Output is correct
3 Correct 238 ms 22180 KB Output is correct
4 Incorrect 245 ms 22188 KB not a zalsequence
5 Incorrect 230 ms 22072 KB not a zalsequence
6 Incorrect 236 ms 22172 KB not a zalsequence
7 Incorrect 238 ms 22052 KB not a zalsequence
8 Incorrect 231 ms 22232 KB not a zalsequence
9 Incorrect 206 ms 20780 KB not a zalsequence
10 Incorrect 128 ms 10964 KB not a zalsequence
11 Incorrect 166 ms 17540 KB not a zalsequence
12 Incorrect 79 ms 6488 KB not a zalsequence
13 Incorrect 86 ms 6352 KB not a zalsequence
14 Incorrect 78 ms 6328 KB not a zalsequence