Submission #647411

#	Time	Username	Problem	Language	Result	Execution time	Memory
647411		Alenygam	Zalmoxis (BOI18_zalmoxis)	C++14	100 / 100	142 ms	29808 KiB

zalmoxis

#include <stack>
#include <stdio.h>
#include <inttypes.h>
#include <sys/stat.h>
#include <sys/mman.h>

using namespace std;

class fio {
	size_t rsize;
	unsigned char* rbuf;
	int ridx;
	
	public:
	fio(FILE* f) : ridx(0) {
		int file = fileno(f);
		struct stat rstat;
		fstat(file, &rstat);
		rsize = rstat.st_size;
		rbuf = (unsigned char*)mmap(0,rsize,PROT_READ,MAP_FILE|MAP_PRIVATE,file,0);
	}
	
	inline bool isBlank() {
	return
		rbuf[ridx] == '\n' || rbuf[ridx] == '\t' || rbuf[ridx] == '\r' ||
		rbuf[ridx] == '\f' || rbuf[ridx] == '\v' || rbuf[ridx] == ' ';
	}
	inline void consumeBlank() { while (isBlank()) ridx++; }
	
	inline void sgravinput(int& res){
		res = 0;
		int flag = 0;
		consumeBlank();
		if (rbuf[ridx] == '-'){
			flag = 1;
			ridx++;
		}
		while (!isBlank() && ridx < rsize)
			res = 10 * res + rbuf[ridx++] - '0';
		res = flag ? -res : res;
	}
};

struct linkedListNode {
	int8_t val;
	linkedListNode *next = nullptr;
	bool splittable = false;
};

linkedListNode preallocLinked[1000001];
int lastNodeLnkd = 0;
inline linkedListNode* get_new_lnkd_node() {
	return &preallocLinked[lastNodeLnkd++];
}

int values[1000010];

fio a(stdin);

int main() {

	int N, K;
	a.sgravinput(N);
	a.sgravinput(K);
	for (int i = 0; i < N; i++) {
		a.sgravinput(values[i]);
	}

	int size = 0;
	linkedListNode *head = get_new_lnkd_node();
	linkedListNode *tail = head;

	stack<int8_t> stck;
	stck.push(30);

	for (int i = 0; i < N; i++) {
		while (stck.top() < values[i]) {
			tail->next = get_new_lnkd_node();
			tail = tail->next;
			tail->val = stck.top();
			tail->splittable = (stck.top() != 0);
			size++;

			stck.pop();
		}

		while (stck.top() > values[i]) {
			int tmp = stck.top()-1;
			stck.pop();
			stck.push(tmp);
			stck.push(tmp);
		}

		tail->next = get_new_lnkd_node();
		tail = tail->next;
		tail->val = values[i];
		tail->splittable = false;
		size++;
		stck.pop();
	}

	while (stck.size()) {
		tail->next = get_new_lnkd_node();
		tail = tail->next;
		tail->val = stck.top();
		tail->splittable = true;
		size++;
		stck.pop();
	}

	linkedListNode *hd = head->next;

	head = head->next;
	while (head != nullptr) {
		while (size < (N + K) && head->splittable) {
			linkedListNode *newNode = get_new_lnkd_node();
			head->val = head->val - 1;

			head->splittable = (head->val != 0);

			newNode->val = head->val;
			newNode->next = head->next;

			newNode->splittable = (newNode->val != 0);
			head->next = newNode;
			size++;
		}
		head = head->next;
	}

	while (hd != nullptr) {
		printf("%d ", (int)hd->val);
		hd = hd->next;
	}
	putchar_unlocked('\n');
}

Compilation message (stderr)

zalmoxis.cpp: In member function 'void fio::sgravinput(int&)':
zalmoxis.cpp:38:29: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   while (!isBlank() && ridx < rsize)
      |                        ~~~~~^~~~~~~

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