Submission #719264

#	Time	Username	Problem	Language	Result	Execution time	Memory
719264		rainboy	Giraffes (JOI22_giraffes)	C11	100 / 100	6496 ms	1208 KiB

giraffes

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

#define N	8000
#define M	(N * 4)
#define INF	0x3f3f3f3f

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

unsigned int X = 12345;

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

int ll[M], rr[M], xx[M], yy[M];

int compare_y(int h1, int h2) {
	return yy[h2] - yy[h1];
}

int compare_r(int h1, int h2) {
	return rr[h2] - rr[h1];
}

int (*compare)(int, int);

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

		while (j < k) {
			int c = compare(hh[j], h);

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

int ft[N * 2 + 1];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] = min(ft[i], x);
		i |= i + 1;
	}
}

int query(int i) {
	int x = INF;

	while (i >= 0) {
		x = min(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int aa[N], ii[N], hh[M], jj[2][2][N], tt[N];
	int n, m, k, h, h_, i, j, a, u, v, l, x, tmp;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		ii[aa[i]] = i;
	}
	m = 0;
	ll[m] = 0, rr[m] = n - 1, xx[m] = 0, yy[m] = n - 1, m++;
	k = 0;
	while (1) {
		for (u = 0; u < 2; u++) {
			for (h = 0; h < m; h++)
				hh[h] = h;
			for (v = 0; v < 2; v++) {
				memset(jj[u][v], 0x3f, n * sizeof *jj[u][v]);
				compare = compare_y, sort(hh, 0, m);
				memset(ft, 0x3f, (n * 2 + 1) * sizeof *ft);
				for (a = n - 1, h = 0; a >= 0; a--) {
					while (h < m && yy[h_ = hh[h]] >= a)
						update(yy[h_] - rr[h_] + n, n * 2 + 1, ll[h_]), h++;
					l = query(a - ii[a] + n);
					if (l != INF)
						jj[u][v][ii[a]] = min(jj[u][v][ii[a]], l);
				}
				compare = compare_r, sort(hh, 0, m);
				memset(ft, 0x3f, (n * 2 + 1) * sizeof *ft);
				for (i = n - 1, h = 0; i >= 0; i--) {
					while (h < m && rr[h_ = hh[h]] >= i)
						update(rr[h_] - yy[h_] + n, n * 2 + 1, xx[h_]), h++;
					x = query(i - aa[i] + n);
					if (x != INF)
						jj[u][v][i] = min(jj[u][v][i], -aa[i] + i + x);
				}
				for (i = 0; i < n; i++) {
					aa[i] = n - 1 - aa[i];
					ii[aa[i]] = i;
				}
				for (h = 0; h < m; h++)
					tmp = n - 1 - xx[h], xx[h] = n - 1 - yy[h], yy[h] = tmp;
			}
			for (a = 0; a < n; a++) {
				ii[a] = n - 1 - ii[a];
				aa[ii[a]] = a;
			}
			for (h = 0; h < m; h++)
				tmp = n - 1 - ll[h], ll[h] = n - 1 - rr[h], rr[h] = tmp;
		}
		for (v = 0; v < 2; v++) {
			for (i = 0; i < n; i++)
				tt[i] = jj[1][v][n - 1 - i] == INF ? -INF : n - 1 - jj[1][v][n - 1 - i];
			memcpy(jj[1][v], tt, n * sizeof *tt);
		}
		m = 0;
		for (i = 0; i < n; i++) {
			if ((j = jj[0][0][i]) <= i)
				ll[m] = j, rr[m] = i - 1, xx[m] = aa[i] - i + j, yy[m] = aa[i] - 1, m++;
			if ((j = jj[0][1][i]) <= i)
				ll[m] = j, rr[m] = i - 1, xx[m] = aa[i] + 1, yy[m] = aa[i] + i - j, m++;
			if ((j = jj[1][0][i]) >= i)
				ll[m] = i + 1, rr[m] = j, xx[m] = aa[i] - j + i, yy[m] = aa[i] - 1, m++;
			if ((j = jj[1][1][i]) >= i)
				ll[m] = i + 1, rr[m] = j, xx[m] = aa[i] + 1, yy[m] = aa[i] + j - i, m++;
		}
		if (m == 0) {
			printf("%d\n", n - k);
			return 0;
		}
		k++;
	}
	return 0;
}

Compilation message (stderr)

giraffes.c: In function 'main':
giraffes.c:74:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
giraffes.c:76:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41