oj.uz

Submission #647440

# Submission time Handle Problem Language Result Execution time Memory
647440 2022-10-02T15:09:29 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 143 ms 31916 KB 
#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];
int lastStck = -1;
int stck[1000];
	
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;

	stck[++lastStck] = 30;

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

			lastStck--;
		}

		while (stck[lastStck] > values[i]) {
			int tmp = stck[lastStck]-1;
			lastStck--;
			stck[++lastStck] = tmp;
			stck[++lastStck] = tmp;
		}

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

		lastStck--;
	}

	while (lastStck >= 0) {
		tail->next = get_new_lnkd_node();
		tail = tail->next;
		tail->val = stck[lastStck];
		tail->splittable = true;
		size++;
		lastStck--;
	}

	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

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

# Verdict Execution time Memory Grader output
1 Correct 114 ms 31916 KB Output is correct
2 Correct 123 ms 31820 KB Output is correct
3 Correct 121 ms 31764 KB Output is correct
4 Correct 120 ms 31752 KB Output is correct
5 Correct 122 ms 31828 KB Output is correct
6 Correct 122 ms 31720 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 31732 KB Output is correct
2 Correct 118 ms 31820 KB Output is correct
3 Correct 118 ms 31840 KB Output is correct
4 Correct 120 ms 31788 KB Output is correct
5 Correct 131 ms 31800 KB Output is correct
6 Correct 143 ms 31720 KB Output is correct
7 Correct 125 ms 31796 KB Output is correct
8 Correct 118 ms 31860 KB Output is correct
9 Correct 118 ms 29388 KB Output is correct
10 Correct 128 ms 27568 KB Output is correct
11 Correct 109 ms 28576 KB Output is correct
12 Correct 95 ms 25776 KB Output is correct
13 Correct 112 ms 25652 KB Output is correct
14 Correct 99 ms 25696 KB Output is correct