제출 #700917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700917		Doncho_Bonboncho	Zalmoxis (BOI18_zalmoxis)	C++14	0 / 100	171 ms	12476 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{
		//	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: 0 / 70