oj.uz

Submission #861860

# Submission time Handle Problem Language Result Execution time Memory
861860 2023-10-17T05:23:59 Z maks007 Zalmoxis (BOI18_zalmoxis) C++14
35 / 100
 1000 ms 168492 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) {
		if(q.size() == 0) break;
		int v = q.top();
		q.pop();
		if(v == 0) {
			ans2.push_back(v);
			continue;
		}
		q.push(v-1);
		q.push(v-1);
	}
	k -= (int)q.size() + (int)ans2.size();
	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:56:9: warning: unused variable 'cnt' [-Wunused-variable]
   56 |  int n, cnt = 0;
      |         ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 25984 KB Output is correct
2 Correct 103 ms 26156 KB Output is correct
3 Correct 103 ms 26156 KB Output is correct
4 Correct 103 ms 27004 KB Output is correct
5 Correct 102 ms 25944 KB Output is correct
6 Correct 102 ms 26076 KB Output is correct

Subtask #2
5.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 51416 KB Expected EOF
2 Correct 103 ms 26252 KB Output is correct
3 Incorrect 171 ms 30444 KB Expected EOF
4 Incorrect 518 ms 85264 KB Expected EOF
5 Incorrect 181 ms 44784 KB Expected EOF
6 Incorrect 270 ms 54976 KB Expected EOF
7 Incorrect 343 ms 67992 KB Expected EOF
8 Incorrect 134 ms 35176 KB Expected EOF
9 Execution timed out 1031 ms 68756 KB Time limit exceeded
10 Execution timed out 1020 ms 55444 KB Time limit exceeded
11 Execution timed out 1047 ms 63776 KB Time limit exceeded
12 Execution timed out 1078 ms 167772 KB Time limit exceeded
13 Execution timed out 1070 ms 168492 KB Time limit exceeded
14 Execution timed out 1069 ms 168060 KB Time limit exceeded