Submission #41402522

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char input_buf[12 + (5 + 12) * 512345];
char* input_pos = input_buf;

static const char* get_line(void) {
	const char* line = input_pos;
	char* next = strchr(input_pos, '\n');
	if (next != NULL) {
		*next = '\0';
		input_pos = next + 1;
	}
	return line;
}

char output_buf[12 * 512345];
char* output_pos = output_buf;

static void out(const char* data) {
	size_t len = strlen(data);
	memcpy(output_pos, data, len);
	output_pos += len;
	*(output_pos++) = ' ';
}

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return a < b ? -1 : a > b;
}

int zac;
int zat[512345];

static int zaq(int q) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zat[m] == q) return m;
		else if (zat[m] < q) l = m + 1;
		else r = m -1;
	}
	printf("ERROR: %d not found\n", q);
	exit(2);
}

int Q;
char op[512345];
const char* arg[512345];
int arg_int[512345];

struct note_node {
	struct note_node* next;
	const char* data;
};

struct note_node nodes[512345];
struct note_node* A;
struct note_node* notebook[512345];

int main(void) {
	int i;
	int zac_raw = 0;
	size_t io_size = 0;
	for (;;) {
		size_t delta = fread(input_buf + io_size, 1, sizeof(input_buf) - io_size, stdin);
		if (delta == 0) break;
		io_size += delta;
	}
	Q = atoi(get_line());
	for (i = 0; i < Q; i++) {
		op[i] = *input_pos;
		switch (*input_pos) {
			case 'A': /* ADD */
				input_pos += 4;
				arg[i] = get_line();
				break;
			case 'D': /* DELETE */
				input_pos += 7;
				break;
			case 'S': /* SAVE */
			case 'L': /* LOAD */
				input_pos += 5;
				zat[zac_raw++] = arg_int[i] = atoi(get_line());
				break;
			default:
				printf("ERROR: %s\n", get_line());
				return 1;
		}
	}

	qsort(zat, zac_raw, sizeof(*zat), cmp);
	zac = 1;
	for (i = 1; i < zac_raw; i++) {
		if (zat[zac - 1] != zat[i]) zat[zac++] = zat[i];
	}

	for (i = 0; i < Q; i++) {
		switch (op[i]) {
			case 'A': /* ADD */
				nodes[i].next = A;
				nodes[i].data = arg[i];
				A = &nodes[i];
				break;
			case 'D': /* DELETE */
				if (A != NULL) A = A->next;
				break;
			case 'S': /* SAVE */
				notebook[zaq(arg_int[i])] = A;
				break;
			case 'L': /* LOAD */
				A = notebook[zaq(arg_int[i])];
				break;
		}
		out(A == NULL ? "-1" : A->data);
	}
	output_pos[-1] = '\n';
	io_size = output_pos - output_buf;
	while (io_size > 0) {
		size_t delta = fwrite(output_pos - io_size, 1, io_size, stdout);
		if (delta == 0) return 3;
		io_size -= delta;
	}
	return 0;
}

/*

クエリを先読みしてページ番号を座標圧縮する
末尾しか参照しない → リストにして末尾のポインタだけ持てばおｋ

高速な方法で入出力を行うことを推奨…？

*/

Submission Info

Judge Result