oj.uz

Submission #861859

# Submission time Handle Problem Language Result Execution time Memory
861859 2023-10-17T05:23:13 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 122 ms 51004 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;
	if(k < 0) {
		while(1){}
	}
	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 104 ms 26036 KB Output is correct
2 Correct 114 ms 25936 KB Output is correct
3 Correct 112 ms 25972 KB Output is correct
4 Correct 105 ms 26188 KB Output is correct
5 Correct 104 ms 26124 KB Output is correct
6 Correct 105 ms 27196 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 25900 KB Expected EOF
2 Correct 104 ms 26156 KB Output is correct
3 Runtime error 79 ms 50748 KB Execution killed with signal 11
4 Incorrect 109 ms 26688 KB Expected EOF
5 Incorrect 105 ms 26092 KB Expected EOF
6 Incorrect 106 ms 26008 KB Expected EOF
7 Incorrect 111 ms 26428 KB Expected EOF
8 Runtime error 122 ms 50596 KB Execution killed with signal 11
9 Runtime error 72 ms 51004 KB Execution killed with signal 11
10 Runtime error 31 ms 23360 KB Execution killed with signal 11
11 Runtime error 47 ms 29756 KB Execution killed with signal 11
12 Runtime error 1 ms 348 KB Execution killed with signal 11
13 Runtime error 1 ms 348 KB Execution killed with signal 11
14 Runtime error 1 ms 348 KB Execution killed with signal 11