Submission #668416

#	Time	Username	Problem	Language	Result	Execution time	Memory
668416		mdubaisi	Zalmoxis (BOI18_zalmoxis)	C++14	0 / 100	21 ms	1612 KiB

zalmoxis

#include <bits/stdc++.h>
#include <array>
#include <unordered_set>
#define ll long long
#define all(v) (v.begin()), (v.end())
#define setall(a, val) for(auto& x : a) x = val
clock_t start_time;
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
void init() {
#ifndef ONLINE_JUDGE
	FILE* _ = freopen("in.txt", "r", stdin);
	start_time = clock();
#endif
}
const ll MOD = 1e9 + 7;
const ll N = 5e6 + 7;
const ll M = 5e1 + 7;
using namespace std;
//####################################################################################

int a[N];
void first_second(stack<int> s, int& x, int& y) {
	if (s.size() < 2) {
		y = -1;
		if (s.size() < 1)
			x = -1;
		else
			x = s.top();
		return;
	}

	x = s.top();
	s.pop();
	y = s.top();
}

void merge(stack<int>& s) {
	int x, y; // cur, prev
	first_second(s, x, y);
	if (y < 0)
		return;

	while (x == y) {
		s.pop();
		s.pop();
		s.push(x + 1);

		first_second(s, x, y);
		if (y < 0)
			return;
	}
}

vector< pair<int, bool> > v; // print, new
void add(stack<int>& s) {
	int x, y;
	first_second(s, x, y); // cur, prev
	v.push_back({ x, 1 });
	s.push(x);
	merge(s);
}

int cnt;
void print(int x, int t) {
	if (!t) {
		cout << x << ' ';
		return;
	}
	else if (x) {
		print(x - 1, 0);
		print(x - 1, t - 1);
		cnt++;
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); srand(time(0));

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];

	stack<int> s;
	s.push(a[0]);
	v.push_back({ a[0], 0 });
	for (int i = 1; i < n; i++) {
		while (a[i] > s.top()) {
			add(s);
			k--;
		}

		v.push_back({ a[i], 0 });
		s.push(a[i]);
		merge(s);
	}
	if (s.size() && k) {
		add(s);
		k--;
	}

	for (pair<int, bool> p : v) {
		cnt = 0;
		print(p.first, p.second * k);
		k -= cnt;
	}
	cout << endl;

	cerr << get_time() << "s" << endl;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'void init()':
zalmoxis.cpp:11:8: warning: unused variable '_' [-Wunused-variable]
   11 |  FILE* _ = freopen("in.txt", "r", stdin);
      |        ^

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