Submission #255150

#	Time	Username	Problem	Language	Result	Execution time	Memory
255150		shayan_p	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	218 ms	34040 KiB

zalmoxis

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn];

int a[maxn];

void go(int &k, int x){
    if(k == 0){
	cout << x << " ";
	return;
    }
    if(x == 0){
	cout << x << " ";
	return;
    }
    k--;
    go(k, x-1);
    go(k, x-1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
	cin >> a[i];
    }
    a[n] = 30;
    int sm = 0;
    for(int i = 0; i < n; i++){
	sm+= 1<<a[i];
	while(__builtin_ctz(sm) < a[i+1])
	    v[i].PB(__builtin_ctz(sm)), sm+= sm & -sm, --k;
    }
    assert(k >= 0);
    for(int i = 0; i < n; i++){
	cout << a[i] << " ";
	for(int x : v[i]){
	    go(k, x);
	}
    }
    return cout << endl, 0;
}

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