제출 #1049496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1049496		rainboy	Bring Down the Grading Server (CEOI23_gradingserver)	C11	65 / 100	4066 ms	166992 KiB

gradingserver

#include <stdio.h>
#include <stdlib.h>
 
#define M	2000000
#define MD	0x7fffffff
#define X	123456789

long long min(long long a, long long b) { return a < b ? a : b; }
 
long long *ek[M]; int *ev[M], eo[M];
 
void init() {
	int h;

	for (h = 0; h < M; h++) {
		ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
		ev[h] = (int *) malloc(2 * sizeof *ev[h]);
	}
}

int hash(long long k) {
	int k1 = k / MD, k2 = k % MD;

	return ((long long) k1 * X + k2) % MD * X % MD % M;
}

void put(long long k, int v) {
	int h = hash(k), o = eo[h]++;

	if (o >= 2 && (o & o - 1) == 0) {
		ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
		ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
	}
	ek[h][o] = k, ev[h][o] = v;
}

int get(long long k) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k)
			return ev[h][o];
	return -1;
}

int c, cnt;

int solve(long long x1, long long y1, long long x2, long long y2) {
	long long y, z;
	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)
		return !solve(x2 - x1, y2, x1, y1);
	if (x1 + y1 * (c - x2) >= c)
		return 1;
	z = x1 >= 0 && x1 <= c && y1 >= 0 && y1 <= c && x2 >= 0 && x2 <= c && y2 >= 0 && y2 <= c ? (((long long) x1 * (c + 1) + y1) * (c + 1) + x2) * (c + 1) + y2 : -1;
	if (z != -1 && (w = get(z)) != -1)
		return w;
	if (cnt < M / 2)
		cnt++;
	else
		z = -1;
	if (!solve(x2 - x1, y2, x1, y1)) {
		if (z != -1)
			put(z, 1);
		return 1;
	}
	w = y1 > 0 && solve(x1 + c - x2, y1 - 1, x2, y2);
	if (z != -1)
		put(z, w);
	return w;
}
 
int main() {
	int t;
 
	init();
	scanf("%d%d", &c, &t);
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

gradingserver.c: In function 'put':
gradingserver.c:30:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
gradingserver.c: In function 'main':
gradingserver.c:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d%d", &c, &t);
      |  ^~~~~~~~~~~~~~~~~~~~~
gradingserver.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   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: 0 / 20
• Subtask 7: 0 / 15