oj.uz

Submission #647414

# Submission time Handle Problem Language Result Execution time Memory
647414 2022-10-02T12:52:30 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 146 ms 30232 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[1000001];
	
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 129 ms 30072 KB Output is correct
2 Correct 118 ms 30156 KB Output is correct
3 Correct 126 ms 30048 KB Output is correct
4 Correct 125 ms 30156 KB Output is correct
5 Correct 132 ms 30156 KB Output is correct
6 Correct 114 ms 30020 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 30076 KB Output is correct
2 Correct 115 ms 30144 KB Output is correct
3 Correct 146 ms 30232 KB Output is correct
4 Correct 116 ms 30144 KB Output is correct
5 Correct 126 ms 30180 KB Output is correct
6 Correct 113 ms 30128 KB Output is correct
7 Correct 129 ms 30172 KB Output is correct
8 Correct 111 ms 30172 KB Output is correct
9 Correct 122 ms 29260 KB Output is correct
10 Correct 102 ms 27256 KB Output is correct
11 Correct 119 ms 27996 KB Output is correct
12 Correct 92 ms 25704 KB Output is correct
13 Correct 103 ms 25684 KB Output is correct
14 Correct 96 ms 25768 KB Output is correct