Submission #1056721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056721		rainboy	Bring Down the Grading Server (CEOI23_gradingserver)	C11	100 / 100	616 ms	994896 KiB

gradingserver

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

#define C	30000
#define R	174	/* R = ceil(sqrt(C)) */
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

int **dpmn[C + 1], **dpmx[C + 1], **dqmn[C + 1], **dqmx[C + 1];
int c;

int solve(long long x1, long long y1, long long x2, long long y2) {
	long long y;
	int w;

	if (x1 + y1 * c <= 0)
		return 0;
	if (x2 + y2 * c <= 0)
		return 1;
	if (x1 <= 0) {
		if (x2 > 0) {
			if (x2 >= c)
				return 0;
			if (y2 > 0) {
				if (x2 - x1 >= c)
					return 0;
				return !solve(x2, y2, x1 + c, y1 - 1);
			}
			y = -x1 / (c - x2) + 1;
			return y <= y1 && solve(x1 + y * (c - x2), y1 - y, x2, y2);
		} else {
			y = min(-x1 / c + 1, -x2 / c + 1);
			return solve(x1 + y * c, y1 - y, x2 + y * c, y2 - y);
		}
	}
	if (x1 >= x2 && (x1 >= c || y1 > 0))
		return 1;
	if (x2 < c && x1 + y1 * (c - x2) >= c)
		return 1;
	if (x2 >= 0 && x2 < c) {
		if (c - x1 >= 0 && c - x1 <= R) {
			if (y2 < dpmn[x2][y1][c - x1])
				return 1;
			if (y2 > dpmx[x2][y1][c - x1])
				return 0;
		}
		if (y2 <= R) {
			if (x1 < dqmn[x2][y1][y2])
				return 0;
			if (x1 > dqmx[x2][y1][y2])
				return 1;
		}
	}
	if (!solve(x2 - x1, y2, x1, y1)) {
		if (x2 >= 0 && x2 < c) {
			if (c - x1 >= 0 && c - x1 <= R)
				dpmn[x2][y1][c - x1] = max(dpmn[x2][y1][c - x1], y2 + 1);
			if (y2 <= R)
				dqmx[x2][y1][y2] = min(dqmx[x2][y1][y2], x1 - 1);
		}
		return 1;
	}
	if (x2 >= c)
		return 0;
	y = y2 == 0 ? 1 : max(min((x2 + c * (y2 - 1)) / (y2 + 1), x2) - x1, 0) / (c - x2) + 1;
	w = y <= y1 && solve(x1 + y * (c - x2), y1 - y, x2, y2);
	if (x2 >= 0 && x2 < c) {
		if (w) {
			if (c - x1 >= 0 && c - x1 <= R)
				dpmn[x2][y1][c - x1] = max(dpmn[x2][y1][c - x1], y2 + 1);
			if (y2 <= R)
				dqmx[x2][y1][y2] = min(dqmx[x2][y1][y2], x1 - 1);
		} else {
			if (c - x1 >= 0 && c - x1 <= R)
				dpmx[x2][y1][c - x1] = min(dpmx[x2][y1][c - x1], y2 - 1);
			if (y2 <= R)
				dqmn[x2][y1][y2] = max(dqmn[x2][y1][y2], x1 + 1);
		}
	}
	return w;
}

int main() {
	int t, x1, y1, x2, y2;

	scanf("%d%d", &c, &t);
	for (x2 = 0; x2 < c; x2++) {
		dpmn[x2] = (int **) malloc((c / (c - x2) + 1) * sizeof *dpmn[x2]);
		dpmx[x2] = (int **) malloc((c / (c - x2) + 1) * sizeof *dpmx[x2]);
		dqmn[x2] = (int **) malloc((c / (c - x2) + 1) * sizeof *dqmn[x2]);
		dqmx[x2] = (int **) malloc((c / (c - x2) + 1) * sizeof *dqmx[x2]);
		for (y1 = 0; y1 * (c - x2) <= c; y1++) {
			dpmn[x2][y1] = (int *) malloc((R + 1) * sizeof *dpmn[x2][y1]);
			dpmx[x2][y1] = (int *) malloc((R + 1) * sizeof *dpmx[x2][y1]);
			dqmn[x2][y1] = (int *) malloc((R + 1) * sizeof *dqmn[x2][y1]);
			dqmx[x2][y1] = (int *) malloc((R + 1) * sizeof *dqmx[x2][y1]);
			for (x1 = 0; x1 <= R; x1++)
				dpmn[x2][y1][x1] = 0, dpmx[x2][y1][x1] = c * 2 + 1;
			for (y2 = 0; y2 <= R; y2++)
				dqmn[x2][y1][y2] = 0, dqmx[x2][y1][y2] = c + 1;
		}
	}
	while (t--) {
		long long x1, y1, x2, y2;

		scanf("%lld%lld%lld%lld", &x1, &y2, &x2, &y1), x1 -= y1 * c, x2 -= y2 * c;
		printf(solve(x1, y1, x2, y2) ? "YES\n" : "NO\n");
	}
	return 0;
}

Compilation message (stderr)

gradingserver.c: In function 'main':
gradingserver.c:88:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  scanf("%d%d", &c, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
gradingserver.c:108:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   scanf("%lld%lld%lld%lld", &x1, &y2, &x2, &y1), x1 -= y1 * c, x2 -= y2 * c;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 5: 25 / 25
• Subtask 4: 20 / 20
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15