oj.uz

Submission #61891

# Submission time Handle Problem Language Result Execution time Memory
61891 2018-07-27T04:36:29 Z 강태규(#1795) Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 398 ms 18688 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 332 ms 18256 KB Output is correct
2 Correct 283 ms 18356 KB Output is correct
3 Correct 323 ms 18356 KB Output is correct
4 Correct 337 ms 18380 KB Output is correct
5 Correct 302 ms 18456 KB Output is correct
6 Correct 330 ms 18644 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 18644 KB Output is correct
2 Correct 316 ms 18660 KB Output is correct
3 Correct 319 ms 18660 KB Output is correct
4 Correct 398 ms 18688 KB Output is correct
5 Correct 255 ms 18688 KB Output is correct
6 Correct 260 ms 18688 KB Output is correct
7 Correct 234 ms 18688 KB Output is correct
8 Correct 262 ms 18688 KB Output is correct
9 Correct 346 ms 18688 KB Output is correct
10 Correct 204 ms 18688 KB Output is correct
11 Correct 282 ms 18688 KB Output is correct
12 Correct 137 ms 18688 KB Output is correct
13 Correct 178 ms 18688 KB Output is correct
14 Correct 183 ms 18688 KB Output is correct