Submission #700920

#	Time	Username	Problem	Language	Result	Execution time	Memory
700920		Doncho_Bonboncho	Zalmoxis (BOI18_zalmoxis)	C++14	5 / 100	145 ms	10432 KiB

zalmoxis

#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 a[MAX_N];

ll paw[32];

int main () {

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

	int n, k;
	std::cin>>n>>k;

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

	ll step = 1;
	for( int i=0 ; i<=30 ; i++ ){
		paw[i] = step;
		step <<= 1;
	}

	std::stack<int> st;
	st.push(30);

	std::vector<int> nas;

	int ind = 0;
	while( ind != n ){
		int curr = st.top();
	//	std::cerr<<curr<<"\n";
		st.pop();
		if( curr == a[ind] ){
			nas.push_back(curr);
			ind++;
		}else{
			if( curr > a[ind] ){
				st.push( curr-1 );
				st.push( curr-1 );
			}else{
			
				nas.push_back( curr );
				/*
		//	std::cerr<<curr<<" "<<paw[curr]<<"\n";
				if( k > paw[curr] ){
					k -= paw[curr];
					for( int i=0 ; i<paw[curr] ; i++ ) nas.push_back(1);
				}else{
					int st = 0;
					while( k ){
						if( k & 1 ){
							for( int i=0 ; i<paw[st] ; i++ ) nas.push_back(curr - st);
						}
						st++;
						k >>= 1;
					}
				}
				*/
			}
		}
	}

	/*
	while( !st.empty()  ){
		int curr = st.top();
		st.pop();
		if( k > paw[curr] ){
					k -= paw[curr];
					for( int i=0 ; i<paw[curr] ; i++ ) nas.push_back(1);
				}else{
					int st = 0;
					while( k ){
						if( k & 1 ){
							for( int i=0 ; i<paw[st] ; i++ ) nas.push_back(curr - st-1);
						}
						st++;
						k >>= 1;
					}
				}


	//	std::cerr<<curr<<"\n";
	}
	*/

	for( auto j : nas ) std::cout<<j<<" ";
	std::cout<<"\n";

	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 5 / 70