oj.uz

Submission #647413

# Submission time Handle Problem Language Result Execution time Memory
647413 2022-10-02T12:51:56 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 42 ms 48084 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];


int main() {
	fio a(fopen("text.txt", "r"));
	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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 47856 KB Execution killed with signal 11
2 Runtime error 31 ms 47960 KB Execution killed with signal 11
3 Runtime error 30 ms 47948 KB Execution killed with signal 11
4 Runtime error 42 ms 47900 KB Execution killed with signal 11
5 Runtime error 35 ms 47956 KB Execution killed with signal 11
6 Runtime error 36 ms 47848 KB Execution killed with signal 11

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 47888 KB Execution killed with signal 11
2 Runtime error 31 ms 47836 KB Execution killed with signal 11
3 Runtime error 29 ms 47868 KB Execution killed with signal 11
4 Runtime error 33 ms 47960 KB Execution killed with signal 11
5 Runtime error 34 ms 47976 KB Execution killed with signal 11
6 Runtime error 35 ms 47948 KB Execution killed with signal 11
7 Runtime error 39 ms 47948 KB Execution killed with signal 11
8 Runtime error 32 ms 47964 KB Execution killed with signal 11
9 Runtime error 32 ms 48000 KB Execution killed with signal 11
10 Runtime error 31 ms 48084 KB Execution killed with signal 11
11 Runtime error 34 ms 47916 KB Execution killed with signal 11
12 Runtime error 35 ms 47884 KB Execution killed with signal 11
13 Runtime error 38 ms 47900 KB Execution killed with signal 11
14 Runtime error 39 ms 47948 KB Execution killed with signal 11