oj.uz

Submission #647441

# Submission time Handle Problem Language Result Execution time Memory
647441 2022-10-02T15:10:04 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 131 ms 29816 KB 
#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[61];
	
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:37:29: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   while (!isBlank() && ridx < rsize)
      |                        ~~~~~^~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 29816 KB Output is correct
2 Correct 125 ms 29692 KB Output is correct
3 Correct 113 ms 29744 KB Output is correct
4 Correct 118 ms 29716 KB Output is correct
5 Correct 115 ms 29788 KB Output is correct
6 Correct 111 ms 29624 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 29688 KB Output is correct
2 Correct 117 ms 29648 KB Output is correct
3 Correct 113 ms 29696 KB Output is correct
4 Correct 125 ms 29732 KB Output is correct
5 Correct 119 ms 29772 KB Output is correct
6 Correct 110 ms 29732 KB Output is correct
7 Correct 124 ms 29712 KB Output is correct
8 Correct 115 ms 29772 KB Output is correct
9 Correct 131 ms 28940 KB Output is correct
10 Correct 112 ms 26956 KB Output is correct
11 Correct 121 ms 27728 KB Output is correct
12 Correct 101 ms 25692 KB Output is correct
13 Correct 100 ms 25672 KB Output is correct
14 Correct 104 ms 25760 KB Output is correct