oj.uz

Submission #861856

# Submission time Handle Problem Language Result Execution time Memory
861856 2023-10-17T05:17:47 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 140 ms 51752 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) {
	queue <int> q;
	vector <int> ans2;
	q.push(v);
	while(q.size() + ans2.size() != k + 1) {
		int v = q.front();
		q.pop();
		if(v == 0) {
			ans2.push_back(v);
			continue;
		}
		q.push(v-1);
		q.push(v-1);
	}
	while(q.size()) {
		int v =q.front();
		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::queue<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 113 ms 26252 KB Output is correct
2 Correct 105 ms 26168 KB Output is correct
3 Correct 105 ms 26684 KB Output is correct
4 Correct 128 ms 26152 KB Output is correct
5 Correct 104 ms 25952 KB Output is correct
6 Correct 103 ms 26256 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 26016 KB Expected EOF
2 Correct 104 ms 25948 KB Output is correct
3 Runtime error 79 ms 48392 KB Execution killed with signal 11
4 Incorrect 105 ms 26152 KB Expected EOF
5 Incorrect 112 ms 26076 KB Expected EOF
6 Incorrect 105 ms 26148 KB Expected EOF
7 Incorrect 106 ms 25996 KB Expected EOF
8 Runtime error 140 ms 51752 KB Execution killed with signal 11
9 Runtime error 73 ms 49208 KB Execution killed with signal 11
10 Runtime error 29 ms 19736 KB Execution killed with signal 11
11 Runtime error 49 ms 33048 KB Execution killed with signal 11
12 Runtime error 1 ms 604 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