oj.uz

Submission #61874

# Submission time Handle Problem Language Result Execution time Memory
61874 2018-07-27T03:52:47 Z koosaga(#1793) Zalmoxis (BOI18_zalmoxis) C++11
40 / 100
 786 ms 16780 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], p[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] == p[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 678 ms 16408 KB Output is correct
2 Correct 553 ms 16408 KB Output is correct
3 Correct 523 ms 16408 KB Output is correct
4 Correct 658 ms 16468 KB Output is correct
5 Correct 641 ms 16548 KB Output is correct
6 Correct 720 ms 16780 KB Output is correct

Subtask #2
10.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 698 ms 16780 KB doesn't contain S as a subsequence
2 Correct 718 ms 16780 KB Output is correct
3 Incorrect 641 ms 16780 KB doesn't contain S as a subsequence
4 Correct 786 ms 16780 KB Output is correct
5 Incorrect 755 ms 16780 KB doesn't contain S as a subsequence
6 Incorrect 567 ms 16780 KB doesn't contain S as a subsequence
7 Incorrect 590 ms 16780 KB doesn't contain S as a subsequence
8 Incorrect 512 ms 16780 KB doesn't contain S as a subsequence
9 Incorrect 483 ms 16780 KB doesn't contain S as a subsequence
10 Incorrect 265 ms 16780 KB doesn't contain S as a subsequence
11 Incorrect 336 ms 16780 KB doesn't contain S as a subsequence
12 Incorrect 141 ms 16780 KB doesn't contain S as a subsequence
13 Incorrect 125 ms 16780 KB doesn't contain S as a subsequence
14 Incorrect 120 ms 16780 KB doesn't contain S as a subsequence