oj.uz

Submission #255871

# Submission time Handle Problem Language Result Execution time Memory
255871 2020-08-02T03:09:59 Z imeimi2000 Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 242 ms 20432 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
int n, k;
int main() {
	scanf("%d%d", &n, &k);
	vector<pii> v;
	vector<int> st;
	
	for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        while (!st.empty() && st.back() < x) {
            v.emplace_back(st.back(), 1);
            --k;
            ++st.back();
            while (st.size() > 1 && st[st.size() - 2] == st[st.size() - 1])
                st.pop_back(), ++st.back();
        }
        v.emplace_back(x, 0);
        st.push_back(x);
        while (st.size() > 1 && st[st.size() - 2] == st[st.size() - 1])
            st.pop_back(), ++st.back();
	}
	while (st.back() < 30) {
        v.emplace_back(st.back(), 1);
        --k;
        ++st.back();
        while (st.size() > 1 && st[st.size() - 2] == st[st.size() - 1])
            st.pop_back(), ++st.back();
	}
	vector<int> ans;
	for (pii i : v) {
        if (i.second) {
            if ((1 << i.first) - 1 <= k) {
                ++k;
                for (int j = (1 << i.first); j--; ) ans.push_back(0), --k;
            }
            else {
                vector<int> use;
                use.push_back(i.first);
                while (k > 0) {
                    int x = use.back();
                    use.pop_back();
                    if (x > 0) {
                        --k;
                        use.push_back(x - 1);
                        use.push_back(x - 1);
                    }
                    else {
                        ans.push_back(0);
                    }
                }
                while (!use.empty()) {
                    ans.push_back(use.back());
                    use.pop_back();
                }
            }
        }
        else ans.push_back(i.first);
	}
	for (int i : ans) {
        printf("%d ", i);
	}
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
zalmoxis.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 20304 KB Output is correct
2 Correct 237 ms 20304 KB Output is correct
3 Correct 233 ms 20432 KB Output is correct
4 Correct 227 ms 20304 KB Output is correct
5 Correct 235 ms 20292 KB Output is correct
6 Correct 242 ms 20432 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 20304 KB Output is correct
2 Correct 229 ms 20304 KB Output is correct
3 Correct 226 ms 20308 KB Output is correct
4 Correct 231 ms 20364 KB Output is correct
5 Correct 238 ms 20432 KB Output is correct
6 Correct 231 ms 20308 KB Output is correct
7 Correct 234 ms 20208 KB Output is correct
8 Correct 227 ms 20404 KB Output is correct
9 Correct 209 ms 19460 KB Output is correct
10 Correct 148 ms 10460 KB Output is correct
11 Correct 185 ms 16672 KB Output is correct
12 Correct 105 ms 6340 KB Output is correct
13 Correct 105 ms 6364 KB Output is correct
14 Correct 108 ms 6492 KB Output is correct