oj.uz

Submission #335435

# Submission time Handle Problem Language Result Execution time Memory
335435 2020-12-12T16:04:26 Z 3funnn Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 720 ms 40432 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pii pair <int, int>
 
using namespace std;
 
int need;
 
void dfs(int val){
    if (need == 0 || val == 0){
        cout << val << " ";
        return;
    }
    --need;
    dfs(val - 1);
    dfs(val - 1);
}
 
int main()
{
    int N, K;
    cin >> N >> K;
    vector <pii> a(N, mp(0, 0));
    for (int i = 0;i < N;++i)
        cin >> a[i].first;
    for (int p = 0;p < 30;++p){
        vector <pii> b;
        for (int i = 0;i < a.size();++i){
            if (a[i].first <= p){
                int j = i, cnt = 0;
                while (j < a.size() && a[j].first <= p){
                    cnt += (1 << a[j].first);
                    b.push_back(a[j]);
                    ++j;
                }
                if ((cnt >> p) & 1)
                    b.push_back(mp(p, 1));
                i = j - 1;
            }
            else
                b.push_back(a[i]);
        }
        a = b;
    }
    need = N + K - a.size();
    for (int i = 0;i < a.size();++i){
        if (a[i].second == 0)
            cout << a[i].first << " ";
        else
            dfs(a[i].first);
    }
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0;i < a.size();++i){
      |                        ~~^~~~~~~~~~
zalmoxis.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                 while (j < a.size() && a[j].first <= p){
      |                        ~~^~~~~~~~~~
zalmoxis.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0;i < a.size();++i){
      |                    ~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 26356 KB Output is correct
2 Correct 700 ms 26652 KB Output is correct
3 Correct 703 ms 26368 KB Output is correct
4 Correct 708 ms 26356 KB Output is correct
5 Correct 720 ms 26340 KB Output is correct
6 Correct 713 ms 26600 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 39900 KB Output is correct
2 Correct 546 ms 37984 KB Output is correct
3 Correct 547 ms 37868 KB Output is correct
4 Correct 622 ms 40084 KB Output is correct
5 Correct 599 ms 40164 KB Output is correct
6 Correct 641 ms 40432 KB Output is correct
7 Correct 628 ms 40092 KB Output is correct
8 Correct 550 ms 37868 KB Output is correct
9 Correct 528 ms 35296 KB Output is correct
10 Correct 296 ms 18748 KB Output is correct
11 Correct 428 ms 28232 KB Output is correct
12 Correct 114 ms 2284 KB Output is correct
13 Correct 109 ms 2284 KB Output is correct
14 Correct 112 ms 2400 KB Output is correct