oj.uz

Submission #861854

# Submission time Handle Problem Language Result Execution time Memory
861854 2023-10-17T05:11:33 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 129 ms 50736 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long

int k;
vector <pair <int,int>> ans;
vector <int> a;

void decomp(int v) {
	stack <int> st;
	st.push(v);
	if(k > (1 << v)) {
		k -= (1 << v);
		for(int i = 0; i < (1 << v); i ++) cout << 0 << " ";
		return;
	}
	while(1) {
		if(st.size() == k + 1) break;
		int v = st.top();
		st.pop();
		if(v == 0) {
			cout << 0 << " ";
			k --;
			continue;
		}
		st.push(v-1);
		st.push(v-1);
	}
	k -= st.size();
	while(!st.empty()) {
		cout << st.top() << " ";
		st.pop();
	}
}

void f(int v) {
	if(a.size() == 0) {
		ans.push_back({v, 1});
		return;
	}
	if(v == a.back()) {
		ans.push_back({v,0});
		a.pop_back();
		return;
	}
	if(a.back() > v) {
		ans.push_back({v,1});
		return;
	}
	f(v-1);
	f(v-1);
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, cnt = 0;
	cin >> n >> k;
	for(int i = 0; i < n; i ++) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	reverse(a.begin(), a.end());

	f(30);
	for(auto i : ans) k -= i.second;
	for(auto i : ans) {
		if(i.second == 0) cout << i.first << " ";
		else if(k){
			decomp(i.first);
		}else cout << i.first << " ";
	}
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'void decomp(long long int)':
zalmoxis.cpp:20:16: warning: comparison of integer expressions of different signedness: 'std::stack<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   20 |   if(st.size() == k + 1) break;
      |      ~~~~~~~~~~^~~~~~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:59:9: warning: unused variable 'cnt' [-Wunused-variable]
   59 |  int n, cnt = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 26668 KB Output is correct
2 Correct 103 ms 26168 KB Output is correct
3 Correct 102 ms 26060 KB Output is correct
4 Correct 102 ms 26156 KB Output is correct
5 Correct 103 ms 26424 KB Output is correct
6 Correct 103 ms 25900 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 48644 KB Execution killed with signal 11
2 Correct 102 ms 26152 KB Output is correct
3 Runtime error 80 ms 48424 KB Execution killed with signal 11
4 Runtime error 77 ms 48420 KB Execution killed with signal 11
5 Runtime error 85 ms 49704 KB Execution killed with signal 11
6 Runtime error 106 ms 49964 KB Execution killed with signal 11
7 Runtime error 129 ms 50736 KB Execution killed with signal 11
8 Runtime error 107 ms 50160 KB Execution killed with signal 11
9 Runtime error 74 ms 48716 KB Execution killed with signal 11
10 Runtime error 61 ms 26340 KB Execution killed with signal 11
11 Runtime error 77 ms 35120 KB Execution killed with signal 11
12 Runtime error 107 ms 4492 KB Execution killed with signal 11
13 Runtime error 105 ms 4520 KB Execution killed with signal 11
14 Runtime error 106 ms 4692 KB Execution killed with signal 11