Submission #366995

#	Time	Username	Problem	Language	Result	Execution time	Memory
366995		rqi	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	433 ms	52772 KiB

zalmoxis

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define sz(x) (int)(x).size()

const int mx = 1000005;
int N, K;

vi additions[mx];
int origS[mx];

void outputSplit(int val){
	if(val == 0){
		cout << val << " ";
		return;
	}
	if(K >= 1){
		K--;
		outputSplit(val-1);
		outputSplit(val-1);
		return;
	}
	cout << val << " ";
}

int main(){
	cin >> N >> K;

	vpi S;
	for(int i = 1; i <= N; i++){
		int x;
		cin >> x;
		S.pb(mp(x, i));
		origS[i] = x;
	}

	for(int val = 0; val <= 29; val++){
		vpi nS;
		for(int i = 0; i < sz(S); i++){
			if(S[i].f != val){
				nS.pb(S[i]);
				continue;
			}
			if(i+1 < sz(S) && S[i].f == S[i+1].f){
				nS.pb(mp(S[i].f+1, S[i+1].s));
				i++;
			}
			else{
				additions[S[i].s].pb(S[i].f);
				nS.pb(mp(S[i].f+1, S[i].s));
			}
		}
		S = nS;

		// cout << val << "\n";

		// for(auto u: S){
		// 	cout << "(" << u.f << ", " << u.s << ") ";
		// }
		// cout << "\n";
	}

	for(int i = 1; i <= N; i++){
		K-=sz(additions[i]);
	}

	for(int i = 1; i <= N; i++){
		cout << origS[i] << " ";
		for(auto u: additions[i]){
			outputSplit(u);
		}
	}
	cout << "\n";
}

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