Submission #700934

#	Time	Username	Problem	Language	Result	Execution time	Memory
700934		Doncho_Bonboncho	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	731 ms	58296 KiB

zalmoxis

#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 (stderr)

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 / 30
• Subtask 2: 70 / 70