paizaラーニングレベルアップ問題集のソートと検索(query)をやってみました。

問題

実行時間制限超過コード

sortingの度に毎回ソートすると、時間がかかります。計算量見積は最大で$O(K(N+K)\log (N+K))$です。

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

int cmp(const void *a, const void *b) {
	return (*(int*) a > *(int*) b) - (*(int*) a < *(int*) b);
}

int main() {
	int N, K, P;
	scanf("%d %d %d", &N, &K, &P);
	int A[N + K];
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	while (K--) {
		char s[8];
		scanf("%s", s);
		if (!strcmp(s, "join")) {
			scanf("%d", &A[N++]);
		} else if (!strcmp(s, "sorting")) {
			qsort(A, N, sizeof(A[0]), cmp);
			for (int i = 0; i <= N; i++) {
				if (i == N || A[i] >= P) {
					printf("%d\n", -~i);
					break;
				}
			}
		}
	}
	return 0;
}

とりあえずリファクタリング

とりあえず

配列をコンストラクタの引数に
クエリをメソッド及びその引数に

したクラスもどきを作成します。

UByteArray.h

#ifndef UBYTEARRAY_H_
#define UBYTEARRAY_H_

#include <stdbool.h>
#include <stdint.h>

typedef struct __UByteArray _UByteArray;

typedef struct UByteArray {
	_UByteArray *_uByteArray;
	bool (*join)(struct UByteArray*, uint8_t);
	size_t (*sorting)(struct UByteArray*);
} UByteArray;

UByteArray* new_UByteArray(size_t, uint8_t*, uint8_t);

void free_UByteArray(UByteArray**);

#endif /* UBYTEARRAY_H_ */

UByteArray.c

#include <stdlib.h>
#include <string.h>
#include "UByteArray.h"

struct __UByteArray{
	uint8_t p;
	size_t n;
	uint8_t A[];
};

static int cmp(const void *a, const void *b) {
	return (*(uint8_t*) a > *(uint8_t*) b) - (*(uint8_t*) a < *(uint8_t*) b);
}

static bool UByteArray_join(UByteArray* uByteArray, uint8_t num) {
	if (num == uByteArray->_uByteArray->p) {
		return false;
	}
	size_t *n = &(uByteArray->_uByteArray->n);
	_UByteArray *tmp = (_UByteArray*) realloc(
		uByteArray->_uByteArray,
		sizeof(_UByteArray) + sizeof(uByteArray->_uByteArray->A[0]) * (*n + 1)
	);
	if (!tmp) {
		free(uByteArray->_uByteArray);
		uByteArray->_uByteArray = NULL;
		return false;
	}
	uByteArray->_uByteArray = tmp;
	uByteArray->_uByteArray->A[(*n)++] = num;
	return true;
}

static size_t UByteArray_sorting(UByteArray* uByteArray) {
	size_t n = uByteArray->_uByteArray->n;
	uint8_t *A = uByteArray->_uByteArray->A;
	uint8_t p = uByteArray->_uByteArray->p;
	qsort(A, n, sizeof(A[0]), cmp);
	for (size_t i = 0; i < n; i++) {
		if (A[i] >= p) {
			return i;
		}
	}
	return n;
}

UByteArray* new_UByteArray(size_t n, uint8_t* a, uint8_t p) {
	UByteArray* uByteArray = (UByteArray*) malloc(sizeof(UByteArray));
	if (!uByteArray) {
		return NULL;
	}
	uByteArray->_uByteArray = (_UByteArray*) malloc(
		sizeof(_UByteArray) + sizeof(uByteArray->_uByteArray->A[0]) * n
	);
	if (!(uByteArray->_uByteArray)) {
		free(uByteArray);
		uByteArray = NULL;
		return NULL;
	}
	uByteArray->_uByteArray->p = p;
	uByteArray->_uByteArray->n = n;
	memcpy(uByteArray->_uByteArray->A, a, sizeof(uByteArray->_uByteArray->A[0]) * n);
	uByteArray->join = UByteArray_join;
	uByteArray->sorting = UByteArray_sorting;
	return uByteArray;
}

void free_UByteArray(UByteArray** uByteArray) {
	free((*uByteArray)->_uByteArray);
	(*uByteArray)->_uByteArray = NULL;
	free(*uByteArray);
	*uByteArray = NULL;
}

そして、main関数を以下のように書き換えます。標準入力の部分は#ifdef NDEBUGで囲んでおきます。※$P=200$の場合が最も処理時間がかかります。

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <inttypes.h>
#include <errno.h>
#include "UByteArray.h"
#ifndef NDEBUG
#include <time.h>
#endif

int main() {
	size_t N, K;
	uint8_t P;
#ifdef NDEBUG
	scanf("%zu %zu %"SCNu8, &N, &K, &P);
#else
	clock_t clockt = clock();
	N = 100000;
	K = 100000;
	P = 200;
#endif
	uint8_t A[N];
	for (size_t i = 0; i < N; i++) {
#ifdef NDEBUG
		scanf("%"SCNu8, &A[i]);
#else
		A[i] = i % 100 + 100;
#endif
	}
	UByteArray *uByteArray = new_UByteArray(N, A, P);
	while (K--) {
		char s[9] = "";
#ifdef NDEBUG
		scanf("%s", s);
#else
		strncpy(s, K % 2 ? "join" : "sorting", sizeof(s));
#endif
		if (!strcmp(s, "join")) {
			uint8_t a;
#ifdef NDEBUG
			scanf("%"SCNu8, &a);
#else
			a = ((K - 1) / 2) % 100 + 100;
#endif
			if (!uByteArray->join(uByteArray, a)) {
				if (!uByteArray->_uByteArray) {
					int e = errno;
					free_UByteArray(&uByteArray);
					perror(NULL);
					return e;
				}
			}
		} else if (!strcmp(s, "sorting")) {
			printf("%zu\n", -~uByteArray->sorting(uByteArray));
		}
	}
	free_UByteArray(&uByteArray);
#ifndef NDEBUG
	fprintf(stderr, "took %f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return 0;
}

Windows環境では、以下のようなバッチを作成しておきます。

main.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 main.c UByteArray.c -o main 1>main.txt 2>&1
if exist main.exe (
	.\main
	del main.exe
	del main.txt
) else (
	type main.txt
)
pause

実行結果

100002
100003
...
106288
106289
続行するには何かキーを押してください . . .

ゲームオーバーになってしまいました

別解

既にお気付きかもしれませんが、paiza君が前から何番目に並ぶことになるかを出力するだけなら、身長$P$cm未満の人数だけカウントすればよいです。
そこで、UByteArray.cを以下のように書き換えます。

UByteArray.c

#include <stdlib.h>
#include <string.h>
#include "UByteArray.h"

struct __UByteArray{
	uint8_t p;
	size_t n;
	size_t rank;
};

static bool UByteArray_join(UByteArray* uByteArray, uint8_t num) {
	if (num == uByteArray->_uByteArray->p) {
		return false;
	}
	if (num < uByteArray->_uByteArray->p) {
		uByteArray->_uByteArray->rank += 1;
	}
	return true;
}

static size_t UByteArray_sorting(UByteArray* uByteArray) {
	return uByteArray->_uByteArray->rank;
}

UByteArray* new_UByteArray(size_t n, uint8_t* a, uint8_t p) {
	UByteArray* uByteArray = (UByteArray*) malloc(sizeof(UByteArray));
	if (!uByteArray) {
		return NULL;
	}
	uByteArray->_uByteArray = (_UByteArray*) malloc(sizeof(_UByteArray));
	if (!(uByteArray->_uByteArray)) {
		free(uByteArray);
		uByteArray = NULL;
		return NULL;
	}
	uByteArray->_uByteArray->p = p;
	uByteArray->_uByteArray->n = n;
	uByteArray->_uByteArray->rank = 0;
	for (size_t i = 0; i < n; i++) {
		if (a[i] < p) {
			uByteArray->_uByteArray->rank += 1;
		}
	}
	uByteArray->join = UByteArray_join;
	uByteArray->sorting = UByteArray_sorting;
	return uByteArray;
}

void free_UByteArray(UByteArray** uByteArray) {
	free((*uByteArray)->_uByteArray);
	(*uByteArray)->_uByteArray = NULL;
	free(*uByteArray);
	*uByteArray = NULL;
}

最早Arrayではない…

実行結果

100002
100003
...
150000
150001
took 28.820999 sec.
続行するには何かキーを押してください . . .

最後まで実行されました

テストコード

今までは、わざと時間をかけるために$P=200$の場合のみやっていました。実際は$100\le P\le 200$の可能性があるので、

$A_i<P$
$A_i>P$

の場合について確かめなければなりません。但し、$A_i=P$は入力されないことになっているし、○番目に含める／含めないとも書いてないので、今回はテスト対象外とします。（普通は、極端な話全員同じ身長だったら、「1番目」となるでしょう。UByteArray.cは一応その前提で実装してあります）
ここで、joinメソッドとsortingメソッドは、試験を完全に分離します。joinの後にsortingをしたらどうなるか、ということは、厳密にいえば結合試験になります。

単体テストツールとしてminunit.hを今回は使用します。

UByteArrayTest.c

#include <stdio.h>
#include <inttypes.h>
#include <stdarg.h>
#include "minunit.h"
#include "UByteArray.h"

int tests_run = 0;

static char* message_u8(uint8_t expected, uint8_t actual) {
	static char msg[80];
	snprintf(msg, sizeof(msg), "Error: expected: <%"PRIu8"> but was: <%"PRIu8">", expected, actual);
	return msg;
}

static char* message_size(size_t expected, size_t actual) {
	static char msg[80];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* test_constructor(size_t expected, uint8_t p, size_t n, ...) {
	va_list ap;
	va_start(ap, n);
	uint8_t A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = (uint8_t) va_arg(ap, unsigned);
	}
	va_end(ap);
	UByteArray *uByteArray = new_UByteArray(n, A, p);
	mu_assert("Error: expected: <not null> but was: <null>", uByteArray);
	void *v = uByteArray->_uByteArray;
	uint8_t q = *(uint8_t*) v;
	v += sizeof(void*);
	size_t size = *(size_t*) v;
	v += sizeof(size_t);
	size_t actual = *(size_t*) v;
	free_UByteArray(&uByteArray);
	mu_assert(message_u8(p, q), q == p);
	mu_assert(message_size(n, size), size == n);
	mu_assert(message_size(expected, actual), actual == expected);
	mu_assert("Error: expected: <null> but was: <not null>", !uByteArray);
	return 0;
}

static char* test_constructor_fail(uint8_t p, size_t n, ...) {
	va_list ap;
	va_start(ap, n);
	uint8_t A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = (uint8_t) va_arg(ap, unsigned);
	}
	va_end(ap);
	UByteArray *uByteArray = new_UByteArray(n, A, p);
	mu_assert("Error: expected: <null> but was: <not null>", !uByteArray);
	return 0;
}

static char* test_constructor_0() {return test_constructor(0, 0, 0);}
static char* test_constructor_1() {return test_constructor_fail(0, 1, 0);}
static char* test_constructor_2() {return test_constructor(1, 1, 1, 0);}
static char* test_constructor_3() {return test_constructor(0, 0, 1, 1);}

static char* test_join(size_t n, uint8_t *A, uint8_t p, uint8_t a) {
	UByteArray *uByteArray = new_UByteArray(n, A, p);
	bool result = uByteArray->join(uByteArray, a);
	free_UByteArray(&uByteArray);
	mu_assert("Error: expected: <true> but was: <false>", result);
	return 0;
}

static char* test_join_fail(size_t n, uint8_t *A, uint8_t p, uint8_t a) {
	UByteArray *uByteArray = new_UByteArray(n, A, p);
	bool result = uByteArray->join(uByteArray, a);
	free_UByteArray(&uByteArray);
	mu_assert("Error: expected: <false> but was: <true>", !result);
	return 0;
}

static char* test_join_0() {return test_join(0, NULL, 0, 1);}
static char* test_join_1() {return test_join_fail(0, NULL, 0, 0);}

static char* test_sorting(size_t expected, uint8_t p, size_t n, ...) {
	va_list ap;
	va_start(ap, n);
	uint8_t A[n];
	for (size_t i = 0; i < n; i++) {
		A[i] = (uint8_t) va_arg(ap, unsigned);
	}
	va_end(ap);
	UByteArray *uByteArray = new_UByteArray(n, A, p);
	mu_assert("Error: expected: <not null> but was: <null>", uByteArray);
	size_t actual = uByteArray->sorting(uByteArray);
	free_UByteArray(&uByteArray);
	mu_assert(message_size(expected, actual), actual == expected);
	return 0;
}

static char* test_sorting_0() {return test_sorting(0, 0, 1, 1);}
static char* test_sorting_1() {return test_sorting(1, 1, 1, 0);}

static char* all_tests() {
	mu_run_test(test_constructor_0);
	mu_run_test(test_constructor_1);
	mu_run_test(test_constructor_2);
	mu_run_test(test_constructor_3);
	mu_run_test(test_join_0);
	mu_run_test(test_join_1);
	mu_run_test(test_sorting_0);
	mu_run_test(test_sorting_1);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

Windows環境の場合、以下のバッチファイルを作っておくと楽に試験が回せるかもしれません。

UByteArrayTest.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 UByteArrayTest.c UByteArray.c -o UByteArrayTest 1>UByteArrayTest.txt 2>&1
if exist UByteArrayTest.exe (
	.\UByteArrayTest
	echo %ERRORLEVEL%
	del UByteArrayTest.exe
	del UByteArrayTest.txt
) else (
	type UByteArrayTest.txt
)
pause

入力チェック

問題集や競技プログラミングでは、制約条件通りの入力が与えられますが、実際はそれ以外の入力が入ってくるかもしれません。数字を入れるべき所に文字を入れてしまうとか。
今回は

$1\le N,K\le 100000$
$100\le P\le 200$
$100\le A_i\le 200$（$1\le i\le N$）
$A_i\neq P$（$1\le i\le N$）
$\text{event}_i$（$1\le i\le K$）は以下のいずれかの形式で与えられる
- join num
  身長 $\text{num}[\text{cm}]$ の生徒がクラスに加入したことを表す
- sorting
  生徒が背の順に並ぶことを表す

という条件が与えられていますが、このうち$A_i\neq P$, $\text{num}\neq P$以外の条件についてチェックします。
（よく読んだら$100\le\text{num}\le 200$とはどこにも書かれていませんでしたが、今回はそのように扱っています。~~レビュー指摘事項ですね~~）

input.h

#ifndef INPUT_H_
#define INPUT_H_

#include <stdbool.h>
#include <inttypes.h>

bool read_size(const char*, size_t*, size_t*, uint8_t*);

bool read_element(const char*, uint8_t*);

bool read_event(const char*, char*, uint8_t*);

#endif /* INPUT_H_ */

input.c

#include <string.h>
#include <ctype.h>
#include <errno.h>
#include "input.h"

static char* chomp(char *str) {
	size_t n = strlen(str);
	while (n--) {
		if (isspace(str[n])) {
			str[n] = '\0';
		} else {
			break;
		}
	}
	return str;
}

static bool is_number(const char *str) {
	if (!(str && *str)) {
		return false;
	}
	if (str[0] == '0') {
		return strlen(str) == 1;
	}
	for (const char *c = str; *c; c++) {
		if (!isdigit(*c)) {
			return false;
		}
	}
	return true;
}

static bool parse(const char *str, uintmax_t *u, uintmax_t max) {
	errno = 0;
	if (!is_number(str)) {
		errno = EINVAL;
		return false;
	}
	char *s = NULL;
	*u = strtoumax(str, &s, 10);
	if (errno) {
		return false;
	} else if (s && *s) {
		errno = EINVAL;
		return false;
	} else if (*u > max) {
		errno = ERANGE;
		return false;
	}
	return true;
}

static bool parse_ulong(const char *str, size_t *n) {
	errno = 0;
	size_t m;
	if (!parse(str, &m, SIZE_MAX)) {
		return false;
	}
	*n = (size_t) m;
	return true;
}

static bool parse_ubyte(const char *str, uint8_t *n) {
	errno = 0;
	uintmax_t m;
	if (!parse(str, &m, UINT8_MAX)) {
		return false;
	}
	*n = (uint8_t) m;
	return true;
}

bool read_size(const char *str, size_t *n, size_t *k, uint8_t *p) {
	errno = 0;
	char s[] = "100000 100000 200\n";
	if (!str || strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	char *t = strtok(chomp(strncpy(s, str, sizeof(s))), " ");
	if (!parse_ulong(t, n)) {
		return false;
	} else if (*n < 1 || 100000 < *n) {
		errno = ERANGE;
		return false;
	}
	t = strtok(NULL, " ");
	if (!parse_ulong(t, k)) {
		return false;
	} else if (*k < 1 || 100000 < *k) {
		errno = ERANGE;
		return false;
	}
	if (!read_element(strtok(NULL, " "), p)) {
		return false;
	}
	t = strtok(NULL, " ");
	if (t) {
		errno = EINVAL;
		return false;
	}
	return true;
}

bool read_element(const char *str, uint8_t *a) {
	errno = 0;
	char s[] = "200\n";
	if (!str || strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	if (!parse_ubyte(chomp(strncpy(s, str, sizeof(s))), a)) {
		return false;
	} else if (*a < 100 || 200 < *a) {
		errno = ERANGE;
		return false;
	}
	return true;
}

bool read_event(const char *str, char *t, uint8_t *n) {
	errno = 0;
	*n = UINT8_MAX;
	char s[] = "join 200\n";
	if (!str || strlen(str) > strlen(s)) {
		errno = EINVAL;
		return false;
	}
	char *u = strtok(chomp(strncpy(s, str, sizeof(s))), " ");
	if (!u) {
		errno = EINVAL;
		return false;
	}
	strncpy(t, u, sizeof("sorting"));
	if (!strcmp(t, "join")) {
		if (!read_element(strtok(NULL, " "), n)) {
			return false;
		}
	} else if (strcmp(t, "sorting")) {
		errno = EINVAL;
		return false;
	}
	if (strtok(NULL, " ")) {
		errno = EINVAL;
		return false;
	}
	return true;
}

テストコード

以上、入力チェックに関するテストコードを記述します。不正な文字や範囲外の入力について弾かれているかどうか、確認します。

inputTest.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "minunit.h"
#include "input.h"

int tests_run = 0;

static char* message_d(int expected, int actual) {
	static char msg[80];
	snprintf(msg, sizeof(msg), "Error: expected: <%d> but was: <%d>", expected, actual);
	return msg;
}

static char* message_u(uint8_t expected, uint8_t actual) {
	static char msg[80];
	snprintf(msg, sizeof(msg), "Error: expected: <%"PRIu8"> but was: <%"PRIu8">", expected, actual);
	return msg;
}

static char* message_z(size_t expected, size_t actual) {
	static char msg[80];
	snprintf(msg, sizeof(msg), "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

 static char* message_s(const char *expected, const char *actual) {
 	static char msg[80];
 	snprintf(msg, sizeof(msg), "Error: expected: <%s> but was: <%s>", expected, actual);
 	return msg;
 }

static char* test_read_size(const char *str, size_t en, size_t ek, uint8_t ep) {
	size_t n, k;
	uint8_t p;
	mu_assert("Error: expected: <true> but was: <false>", read_size(str, &n, &k, &p));
	mu_assert(message_d(errno, 0), errno == 0);
	mu_assert(message_z(en, n), n == en);
	mu_assert(message_z(ek, k), k == ek);
	mu_assert(message_u(ep, p), p == ep);
	return 0;
}

static char* test_read_size_invalid(const char *str) {
	size_t n, k;
	uint8_t p;
	mu_assert("Error: expected: <false> but was: <true>", !read_size(str, &n, &k, &p));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_size_out_of_range(const char *str) {
	size_t n, k;
	uint8_t p;
	mu_assert("Error: expected: <false> but was: <true>", !read_size(str, &n, &k, &p));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_size_0() {return test_read_size_invalid(NULL);}
static char* test_read_size_1() {return test_read_size_invalid("");}
static char* test_read_size_2() {return test_read_size_invalid("1");}
static char* test_read_size_3() {return test_read_size_invalid("1 1");}
static char* test_read_size_4() {return test_read_size_invalid("1 1 100 1");}
static char* test_read_size_5() {return test_read_size_out_of_range("0 1 100");}
static char* test_read_size_6() {return test_read_size_out_of_range("1 0 100");}
static char* test_read_size_7() {return test_read_size_out_of_range("1 1 99");}
static char* test_read_size_8() {return test_read_size("1 1 100", 1, 1, 100);}
static char* test_read_size_9() {return test_read_size("100000 100000 200", 100000, 100000, 200);}
static char* test_read_size_10() {return test_read_size_out_of_range("100001 100000 200");}
static char* test_read_size_11() {return test_read_size_out_of_range("100000 100001 200");}
static char* test_read_size_12() {return test_read_size_out_of_range("100000 100000 201");}
static char* test_read_size_13() {return test_read_size_invalid("100000  100000  200");}

static char* test_read_element(const char *str, uint8_t expected) {
	uint8_t actual;
	mu_assert("Error: expected: <true> but was: <false>", read_element(str, &actual));
	mu_assert(message_d(0, errno), errno == 0);
	mu_assert(message_u(expected, actual), actual == expected);
	return 0;
}

static char* test_read_element_invalid(const char *str) {
	uint8_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_element(str, &actual));
	mu_assert(message_d(EINVAL, errno), errno == EINVAL);
	return 0;
}

static char* test_read_element_out_of_range(const char *str) {
	uint8_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_element(str, &actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_element_0() {return test_read_element_invalid(NULL);}
static char* test_read_element_1() {return test_read_element_invalid("");}
static char* test_read_element_2() {return test_read_element_invalid("-1");}
static char* test_read_element_3() {return test_read_element_out_of_range("0");}
static char* test_read_element_4() {return test_read_element_out_of_range("99");}
static char* test_read_element_5() {return test_read_element("100", 100);}
static char* test_read_element_6() {return test_read_element("200", 200);}
static char* test_read_element_7() {return test_read_element_out_of_range("201");}

static char* test_read_join(const char *str, uint8_t expected) {
	char t[] = "sorting";
	uint8_t actual;
	mu_assert("Error: expected: <true> but was: <false>", read_event(str, t, &actual));
	mu_assert(message_s("join", t), !strcmp(t, "join"));
	mu_assert(message_u(expected, actual), actual == expected);
	return 0;
}

static char* test_read_sorting(const char *str) {
	char t[] = "sorting";
	uint8_t actual;
	mu_assert("Error: expected: <true> but was: <false>", read_event(str, t, &actual));
	mu_assert(message_s("sorting", t), !strcmp(t, "sorting"));
	return 0;
}

static char* test_read_event_invalid(const char *str) {
	char t[] = "sorting";
	uint8_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_event(str, t, &actual));
	mu_assert(message_d(ERANGE, errno), errno == EINVAL);
	return 0;
}

static char* test_read_event_out_of_range(const char *str) {
	char t[] = "sorting";
	uint8_t actual;
	mu_assert("Error: expected: <false> but was: <true>", !read_event(str, t, &actual));
	mu_assert(message_d(ERANGE, errno), errno == ERANGE);
	return 0;
}

static char* test_read_event_0() {return test_read_event_invalid(NULL);}
static char* test_read_event_1() {return test_read_event_invalid("");}
static char* test_read_event_2() {return test_read_event_invalid("join");}
static char* test_read_event_3() {return test_read_event_out_of_range("join 0");}
static char* test_read_event_4() {return test_read_event_out_of_range("join 99");}
static char* test_read_event_5() {return test_read_join("join 100", 100);}
static char* test_read_event_6() {return test_read_join("join 200", 200);}
static char* test_read_event_7() {return test_read_event_out_of_range("join 201");}
static char* test_read_event_8() {return test_read_sorting("sorting");}
static char* test_read_event_9() {return test_read_event_invalid("sorting 100");}

static char* all_tests() {
	mu_run_test(test_read_element_0);
	mu_run_test(test_read_element_1);
	mu_run_test(test_read_element_2);
	mu_run_test(test_read_element_3);
	mu_run_test(test_read_element_4);
	mu_run_test(test_read_element_5);
	mu_run_test(test_read_element_6);
	mu_run_test(test_read_element_7);
	mu_run_test(test_read_size_0);
	mu_run_test(test_read_size_1);
	mu_run_test(test_read_size_2);
	mu_run_test(test_read_size_3);
	mu_run_test(test_read_size_4);
	mu_run_test(test_read_size_5);
	mu_run_test(test_read_size_6);
	mu_run_test(test_read_size_7);
	mu_run_test(test_read_size_8);
	mu_run_test(test_read_size_9);
	mu_run_test(test_read_size_10);
	mu_run_test(test_read_size_11);
	mu_run_test(test_read_size_12);
	mu_run_test(test_read_size_13);
	mu_run_test(test_read_event_0);
	mu_run_test(test_read_event_1);
	mu_run_test(test_read_event_2);
	mu_run_test(test_read_event_3);
	mu_run_test(test_read_event_4);
	mu_run_test(test_read_event_5);
	mu_run_test(test_read_event_6);
	mu_run_test(test_read_event_7);
	mu_run_test(test_read_event_8);
	mu_run_test(test_read_event_9);
	return 0;
}

int main() {
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	return result != 0;
}

inputTest.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 inputTest.c input.c -o inputTest 1>inputTest.txt 2>&1
if exist inputTest.exe (
	.\inputTest
	echo %ERRORLEVEL%
	del inputTest.exe
	del inputTest.txt
) else (
	type inputTest.txt
)
pause

エントリポイント

以上のUByteArray.c、input.cを使って、main関数を書き換えます。先程入力チェックで保留にした$A_i\neq P$等のチェックも入れて、不正な入力の場合には再入力を促します。NDEBUGの定義状態によって、本番用と速度計測用に分けることにします（とゴチャゴチャになってしまった…）

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <inttypes.h>
#include <errno.h>
#include "UByteArray.h"
#ifdef NDEBUG
#include "input.h"
#else
#include <time.h>
#endif

int main() {
	size_t N, K;
	uint8_t P;
#ifdef NDEBUG
	do {
		char s[] = "100000 100000 200\n";
		fgets(s, sizeof(s), stdin);
		if (!strchr(s, '\n')) {
			for (int c = getchar(); !(c == '\0' || c == '\n' || c == EOF); c = getchar());
		} else if (read_size(s, &N, &K, &P)) {
			break;
		}
		perror("The number of elements must be an integer between 1 and 100,000.\n"
				"The number of queries must be an integer between 1 and 100,000.\n"
				"The height must be an integer between 100 and 200.");
	} while (true);
#else
	clock_t clockt = clock();
	N = 100000;
	K = 100000;
	P = 200;
#endif
	uint8_t A[N];
	for (size_t i = 0; i < N; i++) {
#ifdef NDEBUG
		do {
			char s[] = "200\n";
			fgets(s, sizeof(s), stdin);
			if (!strchr(s, '\n')) {
				for (int c = getchar(); !(c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else if (read_element(s, &A[i])) {
				if (A[i] != P) {
					break;
				} else {
					fprintf(stderr, "The height must not be %"PRIu8".\n", P);
					fflush(stderr);
					continue;
				}
			}
			perror("The height must be an integer between 100 and 200.");
		} while (true);
#else
		A[i] = i % 100 + 100;
#endif
	}
	UByteArray *uByteArray = new_UByteArray(N, A, P);
	if (!uByteArray) {
		return errno ? errno : EXIT_FAILURE;
	}
	while (K--) {
		char s[] = "join 200\n";
#ifdef NDEBUG
		do {
			fgets(s, sizeof(s), stdin);
			if (!strchr(s, '\n')) {
				for (int c = getchar(); !(c == '\0' || c == '\n' || c == EOF); c = getchar());
			} else {
#endif
				char t[] = "sorting";
				uint8_t a;
#ifdef NDEBUG
				if (read_event(s, t, &a)) {
#else
		strncpy(t, K % 2 ? "join" : "sorting", sizeof(t));
		a = ((K - 1) / 2) % 100 + 100;
#endif
					if (!strcmp(t, "sorting")) {
						printf("%zu\n", -~uByteArray->sorting(uByteArray));
						fflush(stdout);
#ifdef NDEBUG
						break;
#endif
					} else if (!strcmp(t, "join")) {
						if (uByteArray->join(uByteArray, a)) {
#ifdef NDEBUG
							break;
						} else {
							fprintf(stderr, "The height must not be %"PRIu8".\n", P);
							fflush(stderr);
							continue;
#endif
						}
					}
#ifdef NDEBUG
				}
			}
			perror("Usage: join num or sorting where num is between 100 and 200.");
		} while (true);
#endif
	}
	free_UByteArray(&uByteArray);
#ifndef NDEBUG
	fprintf(stderr, "took %f sec.\n", (float) (clock() - clockt) / CLOCKS_PER_SEC);
#endif
	return 0;
}

テストコード

main関数についても、テストコードを書くことにします。お待ちかねの（？）joinとsortingのシナリオテストも実施することにします。

test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <errno.h>
#include "minunit.h"
#define SOURCE "main"
#define IN_FILE "in.txt"
#define OUT_FILE "out.txt"
#define ERR_FILE "err.txt"

int tests_run = 0;
char result[1000000][8];

static char* message_u(size_t expected, size_t actual) {
	static char msg[80];
	sprintf(msg, "Error: expected: <%zu> but was: <%zu>", expected, actual);
	return msg;
}

static char* message_s(const char *expected, const char *actual) {
	static char msg[80];
	sprintf(msg, "Error: expected: <%s> but was: <%s>", expected, actual);
	return msg;
}

static size_t test(size_t n, const char *lines[]) {
	static unsigned k = 0;
	FILE *file;
	if (!(file = fopen(IN_FILE, "w"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	for (size_t i = 0; i < n; i++) {
		fputs(lines[i], file);
		fputc('\n', file);
	}
	fclose(file);
	clock_t start = clock();
	if (!!(errno = system(".\\" SOURCE " <" IN_FILE " 1>" OUT_FILE " 2>" ERR_FILE))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	fprintf(stderr, "#%u %f sec\n", ++k, (float) (clock() - start) / CLOCKS_PER_SEC);
	fflush(stderr);
	if (!(file = fopen(OUT_FILE, "r"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		exit(errno);
	}
	size_t m = 0;
	while (fgets(result[m], sizeof(result[m]), file)) m++;
	fclose(file);
	return m;
}

static char* test0() {
	const char *lines[] = { "1 1 100", "101", "sorting" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("1\n", result[0]), !strcmp(result[0], "1\n"));
	return 0;
}

static char* test1() {
	const char *lines[] = { "1 1 200", "199", "sorting" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(1, n), n == 1);
	mu_assert(message_s("2\n", result[0]), !strcmp(result[0], "2\n"));
	return 0;
}

static char* test2() {
	const char *lines[] = { "1 3 101", "100", "sorting", "join 102", "sorting" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(2, n), n == 2);
	mu_assert(message_s("2\n", result[0]), !strcmp(result[0], "2\n"));
	mu_assert(message_s("2\n", result[1]), !strcmp(result[1], "2\n"));
	return 0;
}

static char* test3() {
	const char *lines[] = { "1 3 199", "200", "sorting", "join 198", "sorting" };
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(2, n), n == 2);
	mu_assert(message_s("1\n", result[0]), !strcmp(result[0], "1\n"));
	mu_assert(message_s("2\n", result[1]), !strcmp(result[1], "2\n"));
	return 0;
}

static char* test4() {
	const char *lines[] = {
		"100000  100000  200", "1 1 99", "0 0 0", "2 4 150",
		"0000", "201", "99", "150", "100", "200", "100",
		"sorting 200", "join", "join 99", "join 201", "join 150",
		"sorting", "join 100", "join 200", "sorting"
	};
	size_t n = test(sizeof(lines) / sizeof(lines[0]), lines);
	mu_assert(message_u(2, n), n == 2);
	mu_assert(message_s("2\n", result[0]), !strcmp(result[0], "2\n"));
	mu_assert(message_s("3\n", result[1]), !strcmp(result[1], "3\n"));
	return 0;
}

static char* test5() {
	static char *lines[200001] = { "100000 100000 200" };
	size_t k = 1;
	static char _1[100000][4] = {};
	for (size_t i = 0; i < 100000; i++) {
		snprintf(_1[i], sizeof(_1[i]), "%zu", i % 100 + 100);
		lines[k++] = _1[i];
	}
	static char _2[50000][9] = {};
	for (size_t i = 0; i < 50000; i++) {
		snprintf(_2[i], sizeof(_2[i]), "join %zu", i % 100 + 100);
		lines[k++] = _2[i];
		lines[k++] = "sorting";
	}
	size_t n = test(sizeof(lines) / sizeof(lines[0]), (const char**) lines);
	mu_assert(message_u(50000, n), n == 50000);
	for (size_t i = 0; i < 50000; i++) {
		char expected[8];
		snprintf(expected, sizeof(expected), "%zu\n", i + 100002);
		mu_assert(message_s(expected, result[i]), !strcmp(result[i], expected));
	}
	return 0;
}

static char* all_tests() {
	mu_run_test(test0);
	mu_run_test(test1);
	mu_run_test(test2);
	mu_run_test(test3);
	mu_run_test(test4);
	mu_run_test(test5);
	return 0;
}

int main() {
	if (!!(errno = system("gcc -Wall -Wextra -Werror -DNDEBUG -std=c99 " SOURCE ".c UByteArray.c input.c -o " SOURCE " 1>" SOURCE ".txt 2>&1"))) {
		fprintf(stderr, "%s\n", strerror(errno));
		FILE* file = fopen(SOURCE ".txt", "r");
		if (file) {
			int c = 0;
			while ((c = fgetc(file)) != EOF) {
				putchar(c);
			}
			fclose(file);
		}
		return errno;
	}
	char *result = all_tests();
	if (result != 0) {
		fprintf(stderr, "%s\n", result);
		fprintf(stderr, "Tests run: %d\n", tests_run);
	} else {
		fprintf(stdout, "ALL TESTS PASSED\n");
		fprintf(stdout, "Tests run: %d\n", tests_run);
	}
	remove(ERR_FILE);
	remove(OUT_FILE);
	remove(IN_FILE);
	remove(SOURCE ".exe");
	remove(SOURCE ".txt");
	if (errno) {
		return errno;
	} else {
		return result != 0;
	}
}

test.bat

echo off
gcc -Wall -Wextra -Werror -std=c99 test.c -o test 1>test.txt 2>&1
if exist test.exe (
	.\test
	echo %ERRORLEVEL%
	del test.exe
	del test.txt
) else (
	type test.txt
)
pause