Submission #366995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366995	2021-02-16T02:22:09 Z	rqi	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	433 ms	52772 KB

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.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	373 ms	52324 KB	Output is correct
2	Correct	410 ms	52556 KB	Output is correct
3	Correct	377 ms	52400 KB	Output is correct
4	Correct	380 ms	52488 KB	Output is correct
5	Correct	387 ms	52468 KB	Output is correct
6	Correct	369 ms	52044 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	52408 KB	Output is correct
2	Correct	379 ms	52200 KB	Output is correct
3	Correct	406 ms	52576 KB	Output is correct
4	Correct	391 ms	52692 KB	Output is correct
5	Correct	385 ms	52508 KB	Output is correct
6	Correct	382 ms	52408 KB	Output is correct
7	Correct	433 ms	52460 KB	Output is correct
8	Correct	386 ms	52772 KB	Output is correct
9	Correct	340 ms	50932 KB	Output is correct
10	Correct	223 ms	36768 KB	Output is correct
11	Correct	267 ms	40836 KB	Output is correct
12	Correct	124 ms	25836 KB	Output is correct
13	Correct	124 ms	25836 KB	Output is correct
14	Correct	122 ms	25836 KB	Output is correct