oj.uz

Submission #668410

# Submission time Handle Problem Language Result Execution time Memory
668410 2022-12-03T20:05:12 Z mdubaisi Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 3 ms 400 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 n, k, 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 (x < 0 || y < 0)
		return;

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

		first_second(s, x, y);
		if (x < 0 || 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
	if (x < 0)
		return;

	s.push(x);
	v.push_back({ x, 1 });
	merge(s);
}

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

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

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

	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 (v.size() != sz) {
		add(s);
		k--;
	}

	for (pair<int, bool> p : v) {
		int x = p.first;
		bool f = p.second;
		print(x, f * k);
		k *= (!f);
	}
	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);
      |        ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:99:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |  if (v.size() != sz) {
      |      ~~~~~~~~~^~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
2 Incorrect 3 ms 340 KB Unexpected end of file - int32 expected
3 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
4 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
5 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
6 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
2 Incorrect 3 ms 400 KB Unexpected end of file - int32 expected
3 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
4 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
5 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
6 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
7 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
8 Incorrect 3 ms 340 KB Unexpected end of file - int32 expected
9 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
10 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
11 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
12 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
13 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
14 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected