Submission #39248932

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct xy {
  int x;
  int y;
} xy;
int x_cmp (void *n1, void *n2) {
  xy a = *(xy *)n1;
  xy b = *(xy *)n2;
  if (a.x > b.x) {
    return 1;
  } else if (a.x < b.x) {
    return -1;
  } else {
    return 0;
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

typedef struct xy {
	int x;
	int y;
} xy;

int x_cmp (void *n1, void *n2) {
	xy a = *(xy *)n1;
	xy b = *(xy *)n2;
	if (a.x > b.x) {
		return 1;
	} else if (a.x < b.x) {
		return -1;
	} else {
		return 0;
	}
}

int y_cmp (void *n1, void *n2) {
	xy a = *(xy *)n1;
	xy b = *(xy *)n2;
	if (a.y > b.y) {
		return 1;
	} else if (a.y < b.y) {
		return -1;
	} else {
		return 0;
	}
}

void swap_all (void *n1, void *n2, size_t size) {
	char tmp[size];
	memcpy(tmp, n1, size);
	memcpy(n1, n2, size);
	memcpy(n2, tmp, size);
}

void heapsort (void *base, size_t num, size_t size, int (* cmpfunc)(void *, void *), int type) {
	for (int i = 1; num > i; i++) {
		for (int j = i; j > 0;) {
			if (type == 1) {
				if (cmpfunc((char *)(base + size * j), (char *)(base + size * ((j - 1) / 2))) == 1) {
					swap_all((char *)(base + size * j), (char *)(base + size * ((j - 1) / 2)), size);
					j = (j - 1) / 2;
				} else {
					break;
				}
			} else {
				if (cmpfunc((char *)(base + size * j), (char *)(base + size * ((j - 1) / 2))) == -1) {
					swap_all((char *)(base + size * j), (char *)(base + size * ((j - 1) / 2)), size);
					j = (j - 1) / 2;
				} else {
					break;
				}
			}
		}
	}

	for (int i = num - 1; i > 0; i--) {
		swap_all((char *)base, (char *)(base + size * i), size);
		for (int j = 0; ;) {
			int lch = 2 * j + 1, rch = 2 * j + 2, rep;
			if (i > rch) {
				if (type == 1) {
					rep = (cmpfunc((char *)(base + size * lch), (char *)(base + size * rch)) == 1 ? lch : rch);
				} else {
					rep = (cmpfunc((char *)(base + size * lch), (char *)(base + size * rch)) == -1 ? lch : rch);
				}
			} else if (rch == i) {
				rep = lch;
			} else {
				break;
			}
			if (type == 1) {
				if (cmpfunc((char *)(base + size * j), (char *)(base + size * rep)) == -1) {
					swap_all((char *)(base + size * j), (char *)(base + size * rep), size);
					j = rep;
				} else {
					break;
				}
			} else {
				if (cmpfunc((char *)(base + size * j), (char *)(base + size * rep)) == 1) {
					swap_all((char *)(base + size * j), (char *)(base + size * rep), size);
					j = rep;
				} else {
					break;
				}
			}
		}
	}
}

int IsSame (xy a, xy b) {
	if (a.x == b.x && a.y == b.y) {
		return 0;
	}
	return 1;
}

int main (void) {
	int n;
	scanf("%i", &n);

	char s[n + 1];
	scanf("%s", s);

	xy list[n + 1];
	list[0].x = 0;
	list[0].y = 0;

	for (int i = 0; n > i; i++) {
		if (s[i] == 'R') {
			list[i + 1].x = list[i].x + 1;
			list[i + 1].y = list[i].y;
		} else if (s[i] == 'L') {
			list[i + 1].x = list[i].x - 1;
			list[i + 1].y = list[i].y;
		} else if (s[i] == 'U') {
			list[i + 1].y = list[i].y + 1;
			list[i + 1].x = list[i].x;
		} else {
			list[i + 1].y = list[i].y - 1;
			list[i + 1].x = list[i].x;
		}
	}

	heapsort(list, n + 1, sizeof(xy), x_cmp, 1);

	int S = 0, E;
	for (; S <= n + 1;) {
		for (E = S + 1; ; E++) {
			if (E == n + 1) {
				break;
			}
			if (list[S].x != list[E].x) {
				break;
			}
		}
		heapsort(&list[S], E - S, sizeof(xy), y_cmp, 1);
		S = E;
	}

	/*
	for (int i = 0; n + 1 > i; i++) {
		printf("%i %i\n", list[i].x, list[i].y);
	}
	printf("\n");
	// */

	for (int i = 0; n > i; i++) {
		if (IsSame(list[i], list[i + 1]) == 0) {
			printf("Yes\n");
			return 0;
		}
	}

	printf("No\n");

	return 0;
}

Submission Info

Judge Result