oj.uz

Submission #647411

# Submission time Handle Problem Language Result Execution time Memory
647411 2022-10-02T12:32:44 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 142 ms 29808 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];

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

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 123 ms 29716 KB Output is correct
2 Correct 120 ms 29684 KB Output is correct
3 Correct 127 ms 29708 KB Output is correct
4 Correct 119 ms 29712 KB Output is correct
5 Correct 126 ms 29780 KB Output is correct
6 Correct 129 ms 29632 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 29768 KB Output is correct
2 Correct 120 ms 29740 KB Output is correct
3 Correct 119 ms 29808 KB Output is correct
4 Correct 126 ms 29724 KB Output is correct
5 Correct 119 ms 29724 KB Output is correct
6 Correct 131 ms 29728 KB Output is correct
7 Correct 120 ms 29796 KB Output is correct
8 Correct 142 ms 29800 KB Output is correct
9 Correct 117 ms 29004 KB Output is correct
10 Correct 121 ms 26956 KB Output is correct
11 Correct 112 ms 27692 KB Output is correct
12 Correct 105 ms 25704 KB Output is correct
13 Correct 98 ms 25820 KB Output is correct
14 Correct 107 ms 25700 KB Output is correct