oj.uz

Submission #861861

# Submission time Handle Problem Language Result Execution time Memory
861861 2023-10-17T05:24:27 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 124 ms 50400 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 26152 KB Output is correct
2 Correct 105 ms 26152 KB Output is correct
3 Correct 110 ms 26380 KB Output is correct
4 Correct 105 ms 26016 KB Output is correct
5 Correct 104 ms 26156 KB Output is correct
6 Correct 104 ms 26064 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 26108 KB Expected EOF
2 Correct 104 ms 26216 KB Output is correct
3 Runtime error 78 ms 48428 KB Execution killed with signal 11
4 Incorrect 104 ms 26248 KB Expected EOF
5 Incorrect 106 ms 26032 KB Expected EOF
6 Incorrect 106 ms 26036 KB Expected EOF
7 Incorrect 104 ms 25992 KB Expected EOF
8 Runtime error 124 ms 50400 KB Execution killed with signal 11
9 Runtime error 69 ms 47128 KB Execution killed with signal 11
10 Runtime error 32 ms 24900 KB Execution killed with signal 11
11 Runtime error 47 ms 31248 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 1 ms 348 KB Execution killed with signal 11