oj.uz

Submission #61889

# Submission time Handle Problem Language Result Execution time Memory
61889 2018-07-27T04:32:54 Z 강태규(#1795) Zalmoxis (BOI18_zalmoxis) C++11
65 / 100
 387 ms 18712 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) <= 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 278 ms 18304 KB Output is correct
2 Correct 263 ms 18432 KB Output is correct
3 Correct 247 ms 18488 KB Output is correct
4 Correct 262 ms 18556 KB Output is correct
5 Correct 350 ms 18632 KB Output is correct
6 Correct 297 ms 18712 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 18712 KB Output is correct
2 Correct 387 ms 18712 KB Output is correct
3 Incorrect 312 ms 18712 KB Unexpected end of file - int32 expected
4 Correct 339 ms 18712 KB Output is correct
5 Correct 310 ms 18712 KB Output is correct
6 Correct 333 ms 18712 KB Output is correct
7 Correct 274 ms 18712 KB Output is correct
8 Correct 331 ms 18712 KB Output is correct
9 Incorrect 239 ms 18712 KB Unexpected end of file - int32 expected
10 Incorrect 219 ms 18712 KB Unexpected end of file - int32 expected
11 Incorrect 218 ms 18712 KB Unexpected end of file - int32 expected
12 Incorrect 193 ms 18712 KB Unexpected end of file - int32 expected
13 Incorrect 169 ms 18712 KB Unexpected end of file - int32 expected
14 Incorrect 121 ms 18712 KB Unexpected end of file - int32 expected