oj.uz

Submission #700934

# Submission time Handle Problem Language Result Execution time Memory
700934 2023-02-19T12:52:07 Z Doncho_Bonboncho Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 731 ms 58296 KB 
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6 + 42;
const int INF = 1e9;
const int mod = 1e9 + 7;

int n, k;
int a[MAX_N];

int ind = 0;
std::vector<ll> nas;

std::set<ll> s;

void sol( ll x, int level ){
	if( level == a[ind] ){
		nas.push_back(x);
		ind++;
		return ;
	}
	sol( 2*x, level -1 );
	if( ind >= n or level <= a[ind] ){
		s.insert( 2*x +1 );
		return ;
	}
	sol( 2*x +1, level-1 );
}

void print_nas( ll x, int level ){
	if( std::binary_search( nas.begin(), nas.end(), x ) ){
		std::cout<<level<<" ";
		return ;
	}
	print_nas( 2*x, level-1 );
	print_nas( 2*x +1, level-1 );
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	std::cin>>n>>k;

	for( int i=0 ; i<n ; i++ ) std::cin>>a[i];

	sol( 1, 30 );

	while( s.size() < k ){
		int curr = *s.begin();
		s.erase( curr );
		s.insert( curr * 2 );
		s.insert( curr * 2 +1);
	}

	for( auto &j : s ) nas.push_back( j );
	std::sort( nas.begin(), nas.end() );

	/*
	for( auto j : nas ) std::cerr<<j<<" ";
	std::cerr<<"\n\n";
	*/

	print_nas( 1, 30 );

	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:52:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |  while( s.size() < k ){
      |         ~~~~~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 14368 KB Output is correct
2 Correct 321 ms 14396 KB Output is correct
3 Correct 317 ms 14320 KB Output is correct
4 Correct 336 ms 14508 KB Output is correct
5 Correct 331 ms 14380 KB Output is correct
6 Correct 330 ms 14464 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 14404 KB Output is correct
2 Correct 326 ms 14396 KB Output is correct
3 Correct 323 ms 14384 KB Output is correct
4 Correct 316 ms 14352 KB Output is correct
5 Correct 322 ms 14380 KB Output is correct
6 Correct 356 ms 14364 KB Output is correct
7 Correct 332 ms 14340 KB Output is correct
8 Correct 359 ms 14380 KB Output is correct
9 Correct 357 ms 22984 KB Output is correct
10 Correct 544 ms 44864 KB Output is correct
11 Correct 457 ms 36092 KB Output is correct
12 Correct 703 ms 58296 KB Output is correct
13 Correct 731 ms 58256 KB Output is correct
14 Correct 695 ms 58156 KB Output is correct