Submission #1241482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241482		Amaarsaa	Zalmoxis (BOI18_zalmoxis)	C++20	100 / 100	155 ms	18384 KiB

zalmoxis

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 1e6;

int main(){
	ll n, m, r, i, cnt, S, x, s, p;
	cin >> n >> m;

	stack < ll > st;

	p = 0;
	ll a[n + 2];

	for (i = 1; i <= n; i ++) cin >> a[i];
	vector < ll > v;
	vector < bool >q;
	for (i = 1; i <= n; i ++) {
		r = 1<<a[i];
		s = (p + r - 1)/r;
		s = s * r;
		S = s + r;
		while ( p < s) {
			ll P = p;
			r = 1;
			cnt = 0;
			while ( P % 2 == 0) {
				P/= 2;
				r = r * 2;
				cnt ++;
			}
			p += r;
			v.push_back(cnt);
			q.push_back(1);
		}
		v.push_back(a[i]);
		q.push_back(0);
		p = S;
	}
	while ( p < 1073741824) {
			ll P = p;
			r = 1;
			cnt = 0;
			while ( P % 2 == 0) {
				P/= 2;
				r = r * 2;
				cnt ++;
			}
			p += r;
			v.push_back(cnt);
			q.push_back(1);
	}
	n = n + m - v.size();
	for (i = 0; i < v.size(); i ++) {
		if ( q[i] == 1) {
			stack < ll > S;
			S.push(v[i]);
			while ( n > 0 && !S.empty()) {
				if ( S.top() == 0) {
					cout << 0 << " ";
					S.pop();
					continue;
				}
				r = S.top();
				n --;
				S.pop();
				S.push(r - 1);
				S.push(r - 1);
			}
			while ( !S.empty()) {
				x = S.top();
				if ( x < 0) while(1);
				cout << x << " ";
				S.pop();
			}
		}
		else {
			if ( v[i] < 0) {
				while(1);
			}
			cout << v[i] << " ";
		}
	}
	cout << endl;
}

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