Submission #255871

#	Time	Username	Problem	Language	Result	Execution time	Memory
255871		imeimi2000	Zalmoxis (BOI18_zalmoxis)	C++17	100 / 100	242 ms	20432 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70