oj.uz

Submission #431220

# Submission time Handle Problem Language Result Execution time Memory
431220 2021-06-17T10:23:28 Z faresbasbs Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 501 ms 16404 KB 
#include<bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 1000050;

int n, k, a[MAXN];

int dfs(int x, int c){
	if(x == 0 || c == 1){
		cout << x << " ";
		return 1;
	}
	else{
		int x1 = dfs(x - 1, c / 2);
		int x2 = dfs(x - 1, (c + 1) / 2);
		return x1 + x2;
	}
}

int main(){
	cin >> n >> k;
	vector<int> v;
	for(int i=0; i<n; i++){
		cin >> a[i];
		v.push_back(a[i]);
	}
	for(int i=0; i<30; i++){
		vector<int> b;
		for(int j=0; j<v.size(); ){
			if(v[j] > i){
				b.push_back(v[j]);
				j++;
			}
			else{
				int e = j;
				int ans = 0;
				while(e < v.size() && v[e] <= i){
					ans += (1 << v[e]);
					e++;
				}
				for(int k=j; k<e; k++){
					b.push_back(v[k]);
				}
				if((ans >> i) & 1) b.push_back(i);
				j = e;
			}
		}
		v = b;
	}
	int ptr = 0;
	int needy = n + k - (int)v.size();
	assert(needy >= 0);
	for(int i=0; i<v.size(); i++){
		if(ptr < n && v[i] == a[ptr]){
			cout << v[i] << " ";
			ptr++;
		}
		else{
			needy -= dfs(v[i], needy + 1) - 1;
		}
	}
	cout << endl;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:30:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int j=0; j<v.size(); ){
      |                ~^~~~~~~~~
zalmoxis.cpp:38:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while(e < v.size() && v[e] <= i){
      |           ~~^~~~~~~~~~
zalmoxis.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0; i<v.size(); i++){
      |               ~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 16404 KB Output is correct
2 Correct 495 ms 16180 KB Output is correct
3 Correct 469 ms 16260 KB Output is correct
4 Correct 466 ms 16292 KB Output is correct
5 Correct 474 ms 16232 KB Output is correct
6 Correct 462 ms 16236 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 16212 KB Output is correct
2 Correct 476 ms 16200 KB Output is correct
3 Correct 469 ms 16288 KB Output is correct
4 Correct 474 ms 16196 KB Output is correct
5 Correct 501 ms 16320 KB Output is correct
6 Correct 466 ms 16280 KB Output is correct
7 Correct 476 ms 16240 KB Output is correct
8 Correct 482 ms 16188 KB Output is correct
9 Correct 450 ms 14924 KB Output is correct
10 Correct 237 ms 6984 KB Output is correct
11 Correct 308 ms 15768 KB Output is correct
12 Correct 111 ms 2208 KB Output is correct
13 Correct 110 ms 2216 KB Output is correct
14 Correct 108 ms 2176 KB Output is correct