Submission #544603

#	Time	Username	Problem	Language	Result	Execution time	Memory
544603		rainboy	Fliper (COCI22_fliper)	C11	110 / 110	600 ms	87400 KiB

Main

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

#define N	500000
#define N_	(N * 2 + 1)

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int xx[N], yy[N], ii[N], jj[N], uu[N * 2];

int compare_xy(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j]; }
int compare_yx(int i, int j) { return yy[i] != yy[j] ? yy[i] - yy[j] : xx[i] - xx[j]; }

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ds[N_];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int *eh[N_], eo[N_], eo_[N_];
char used[N], aa[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int a;

void dfs(int i) {
	while (eo_[i] < eo[i]) {
		int h = eh[i][eo_[i]++];

		if (!used[h])
			used[h] = 1, dfs(i ^ uu[h << 1 | 0] ^ uu[h << 1 | 1]), aa[h] = a ^= 1;
	}
}

int main() {
	static char cc[N];
	static int kk[N_];
	int n, i, j, r, u;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		static char s[2];

		scanf("%d%d%s", &xx[i], &yy[i], s);
		cc[i] = s[0];
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	memset(ds, -1, (n * 2 + 1) * sizeof *ds);
	compare = compare_xy, sort(ii, 0, n);
	for (i = 0; i <= n; i++)
		if (i > 0 && i < n && xx[ii[i]] == xx[ii[i - 1]])
			join(ii[i - 1] << 1 | (cc[ii[i - 1]] == '/' ? 0 : 1),
					ii[i] << 1 | (cc[ii[i]] == '\\' ? 0 : 1));
		else {
			if (i > 0)
				join(ii[i - 1] << 1 | (cc[ii[i - 1]] == '/' ? 0 : 1), n * 2);
			if (i < n)
				join(ii[i] << 1 | (cc[ii[i]] == '\\' ? 0 : 1), n * 2);
		}
	for (j = 0; j < n; j++)
		jj[j] = j;
	compare = compare_yx, sort(jj, 0, n);
	for (j = 0; j <= n; j++)
		if (j > 0 && j < n && yy[jj[j]] == yy[jj[j - 1]])
			join(jj[j - 1] << 1 | 1, jj[j] << 1 | 0);
		else {
			if (j > 0)
				join(jj[j - 1] << 1 | 1, n * 2);
			if (j < n)
				join(jj[j] << 1 | 0, n * 2);
		}
	for (i = 0; i < n * 2; i++)
		kk[uu[i] = find(i)]++;
	u = find(n * 2);
	for (i = 0; i <= n * 2; i++)
		if (i != u && ds[i] < 0 && kk[i] % 8 != 0) {
			printf("-1\n");
			return 0;
		}
	memset(ds, -1, n * 2 * sizeof *ds);
	for (i = 0; i <= n; i++)
		if (i > 0 && i < n && xx[ii[i]] == xx[ii[i - 1]]
				&& uu[ii[i - 1] << 1 | (cc[ii[i - 1]] == '/' ? 0 : 1)] != u)
			join(ii[i - 1] << 1 | 0, ii[i] << 1 | 1), join(ii[i - 1] << 1 | 1, ii[i] << 1 | 0);
	for (j = 0; j <= n; j++)
		if (j > 0 && j < n && yy[jj[j]] == yy[jj[j - 1]] && uu[jj[j - 1] << 1 | 1] != u)
			join(jj[j - 1] << 1 | 0, jj[j] << 1 | 1), join(jj[j - 1] << 1 | 1, jj[j] << 1 | 0);
	for (r = 0; r < 2; r++) {
		for (i = 0; i <= n * 2; i++)
			eh[i] = (int *) malloc(2 * sizeof *eh[i]), eo[i] = eo_[i] = 0;
		memset(used, 0, n * sizeof *used);
		for (i = 0; i < n; i++)
			if ((find(i << 1 | 0) < find(i << 1 | 1)) == (r == 0))
				append(uu[i << 1 | 0], i), append(uu[i << 1 | 1], i);
		a = 0;
		dfs(u);
		for (i = 0; i <= n * 2; i++)
			dfs(i);
		for (i = 0; i <= n * 2; i++)
			free(eh[i]);
	}
	for (i = 0; i < n; i++)
		printf("%d ", (aa[i] << 1 | (find(i << 1 | 0) < find(i << 1 | 1) ? 0 : 1)) + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:69:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   69 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d%d%s", &xx[i], &yy[i], s);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70