oj.uz

Submission #61876

# Submission time Handle Problem Language Result Execution time Memory
61876 2018-07-27T03:55:50 Z koosaga(#1793) Zalmoxis (BOI18_zalmoxis) C++11
100 / 100
 655 ms 16676 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){
		printf("%d ", 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++){
		scanf("%d",&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]){
			printf("%d ", v[i]);
			ptr++;
		}
		else{
			needy -= dfs(v[i], needy + 1) - 1;
		}
	}
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); ){
                ~^~~~~~~~~
zalmoxis.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(e < v.size() && v[e] <= i){
           ~~^~~~~~~~~~
zalmoxis.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
zalmoxis.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 16372 KB Output is correct
2 Correct 655 ms 16372 KB Output is correct
3 Correct 619 ms 16568 KB Output is correct
4 Correct 546 ms 16616 KB Output is correct
5 Correct 544 ms 16616 KB Output is correct
6 Correct 510 ms 16644 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 16644 KB Output is correct
2 Correct 525 ms 16644 KB Output is correct
3 Correct 648 ms 16644 KB Output is correct
4 Correct 581 ms 16668 KB Output is correct
5 Correct 647 ms 16668 KB Output is correct
6 Correct 627 ms 16676 KB Output is correct
7 Correct 596 ms 16676 KB Output is correct
8 Correct 574 ms 16676 KB Output is correct
9 Correct 555 ms 16676 KB Output is correct
10 Correct 331 ms 16676 KB Output is correct
11 Correct 373 ms 16676 KB Output is correct
12 Correct 121 ms 16676 KB Output is correct
13 Correct 117 ms 16676 KB Output is correct
14 Correct 153 ms 16676 KB Output is correct