oj.uz

Submission #861857

# Submission time Handle Problem Language Result Execution time Memory
861857 2023-10-17T05:18:22 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 126 ms 50472 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> q;
	vector <int> ans2;
	q.push(v);
	while(q.size() + ans2.size() != k + 1) {
		int v = q.top();
		q.pop();
		if(v == 0) {
			ans2.push_back(v);
			continue;
		}
		q.push(v-1);
		q.push(v-1);
	}
	while(q.size()) {
		int v =q.top();
		q.pop();
		ans2.push_back(v);
	} 
	for(auto i : ans2) cout << i << " ";
}

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:15:31: 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]
   15 |  while(q.size() + ans2.size() != k + 1) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:54:9: warning: unused variable 'cnt' [-Wunused-variable]
   54 |  int n, cnt = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 25984 KB Output is correct
2 Correct 103 ms 26664 KB Output is correct
3 Correct 103 ms 26156 KB Output is correct
4 Correct 103 ms 26028 KB Output is correct
5 Correct 105 ms 26412 KB Output is correct
6 Correct 104 ms 26912 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 26024 KB Expected EOF
2 Correct 104 ms 25940 KB Output is correct
3 Runtime error 77 ms 48428 KB Execution killed with signal 11
4 Incorrect 105 ms 26152 KB Expected EOF
5 Incorrect 105 ms 26156 KB Expected EOF
6 Incorrect 104 ms 26024 KB Expected EOF
7 Incorrect 107 ms 26152 KB Expected EOF
8 Runtime error 126 ms 50472 KB Execution killed with signal 11
9 Runtime error 69 ms 47660 KB Execution killed with signal 11
10 Runtime error 31 ms 23568 KB Execution killed with signal 11
11 Runtime error 54 ms 32824 KB Execution killed with signal 11
12 Runtime error 1 ms 600 KB Execution killed with signal 11
13 Runtime error 1 ms 600 KB Execution killed with signal 11
14 Runtime error 1 ms 344 KB Execution killed with signal 11