oj.uz

Submission #668416

# Submission time Handle Problem Language Result Execution time Memory
668416 2022-12-03T20:14:22 Z mdubaisi Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 21 ms 1612 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
2 Incorrect 20 ms 1484 KB Unexpected end of file - int32 expected
3 Incorrect 19 ms 1480 KB Unexpected end of file - int32 expected
4 Incorrect 19 ms 1492 KB Unexpected end of file - int32 expected
5 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
6 Incorrect 20 ms 1484 KB Unexpected end of file - int32 expected

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
2 Incorrect 20 ms 1424 KB Unexpected end of file - int32 expected
3 Incorrect 21 ms 1612 KB Unexpected end of file - int32 expected
4 Incorrect 20 ms 1484 KB Unexpected end of file - int32 expected
5 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
6 Incorrect 19 ms 1448 KB Unexpected end of file - int32 expected
7 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
8 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
9 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
10 Incorrect 19 ms 1532 KB Unexpected end of file - int32 expected
11 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected
12 Incorrect 20 ms 1488 KB Unexpected end of file - int32 expected
13 Incorrect 19 ms 1536 KB Unexpected end of file - int32 expected
14 Incorrect 19 ms 1484 KB Unexpected end of file - int32 expected