oj.uz

답안 #647445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647445 2022-10-02T15:32:23 Z Alenygam Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 131 ms 29904 KB 
#include <stdio.h>
#include <inttypes.h>
#include <sys/stat.h>
#include <sys/mman.h>

#ifdef EVAL
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;
	}
};
#else
#include <iostream>
class fio {
	public:
	fio (FILE* f) {}
	inline void sgravinput(int & res) {
		std::cin >> res;
	}
};
#endif

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--;
	}

	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++;
		}
		printf("%d ", (int)head->val);
		head = head->next;
	}
	putchar_unlocked('\n');
}

Compilation message

zalmoxis.cpp: In member function 'void fio::sgravinput(int&)':
zalmoxis.cpp:36:29: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while (!isBlank() && ridx < rsize)
      |                        ~~~~~^~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 29772 KB Output is correct
2 Correct 113 ms 29804 KB Output is correct
3 Correct 131 ms 29684 KB Output is correct
4 Correct 125 ms 29756 KB Output is correct
5 Correct 115 ms 29692 KB Output is correct
6 Correct 131 ms 29904 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 29656 KB Output is correct
2 Correct 126 ms 29648 KB Output is correct
3 Correct 115 ms 29772 KB Output is correct
4 Correct 131 ms 29748 KB Output is correct
5 Correct 110 ms 29672 KB Output is correct
6 Correct 115 ms 29676 KB Output is correct
7 Correct 113 ms 29684 KB Output is correct
8 Correct 110 ms 29720 KB Output is correct
9 Correct 121 ms 28952 KB Output is correct
10 Correct 115 ms 26944 KB Output is correct
11 Correct 113 ms 27688 KB Output is correct
12 Correct 107 ms 25652 KB Output is correct
13 Correct 117 ms 25676 KB Output is correct
14 Correct 103 ms 25764 KB Output is correct