oj.uz

Submission #861858

# Submission time Handle Problem Language Result Execution time Memory
861858 2023-10-17T05:22:43 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 123 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);
	// assert()
	// for(auto i : ans) cout << i.first << " ";
		
	for(auto i : ans) k -= i.second;
		assert(k >= 0);
	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 26152 KB Output is correct
2 Correct 104 ms 26156 KB Output is correct
3 Correct 107 ms 26176 KB Output is correct
4 Correct 106 ms 26140 KB Output is correct
5 Correct 104 ms 26668 KB Output is correct
6 Correct 111 ms 26016 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 26340 KB Expected EOF
2 Correct 105 ms 26092 KB Output is correct
3 Runtime error 81 ms 48372 KB Execution killed with signal 11
4 Incorrect 105 ms 26376 KB Expected EOF
5 Incorrect 104 ms 26000 KB Expected EOF
6 Incorrect 104 ms 26176 KB Expected EOF
7 Incorrect 105 ms 26140 KB Expected EOF
8 Runtime error 123 ms 50472 KB Execution killed with signal 11
9 Runtime error 68 ms 46168 KB Execution killed with signal 11
10 Runtime error 30 ms 20736 KB Execution killed with signal 11
11 Runtime error 47 ms 31292 KB Execution killed with signal 11
12 Runtime error 1 ms 600 KB Execution killed with signal 11
13 Runtime error 1 ms 348 KB Execution killed with signal 11
14 Runtime error 0 ms 348 KB Execution killed with signal 11