Submission #486977

#	Time	Username	Problem	Language	Result	Execution time	Memory
486977		rainboy	Raspad (COI17_raspad)	C11	100 / 100	388 ms	108228 KiB

raspad

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

#define N	100000
#define M	50

int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, -1, 0, 1 };

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

int cross(int x1, int y1, int x2, int y2) {
	return x1 * y2 - x2 * y1;
}

int main() {
	static char cc[N][M + 1], visited[N * M * 4];
	static int nxt[N * M * 4];
	int n, m, h, h_, i, i_, j, j_, ijh;
	long long ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	ans = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '1') {
				ans += (long long) (i + 1) * (n - i);
				if (j > 0 && cc[i][j - 1] == '1')
					ans -= (long long) (i + 1) * (n - i);
				if (i > 0 && cc[i - 1][j] == '1')
					ans -= (long long) i * (n - i);
			}
	memset(nxt, -1, n * m * 4 * sizeof *nxt);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '1')
				for (h = 0; h < 4; h++) {
					i_ = i - di[h], j_ = j - dj[h];
					if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == '1')
						for (h_ = (h + 3) % 4; ; h_ = (h_ + 1) % 4) {
							i_ = i + di[h_], j_ = j + dj[h_];
							if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == '1') {
								nxt[(i * m + j) * 4 + h] = (i_ * m + j_) * 4 + h_;
								break;
							}
						}
				}
	for (ijh = 0; ijh < n * m * 4; ijh++)
		if (nxt[ijh] != -1 && !visited[ijh]) {
			int imn, imx, a;

			imn = n, imx = -1, a = 0;
			while (!visited[ijh]) {
				visited[ijh] = 1;
				i = ijh / 4 / m, j = ijh / 4 % m, h = ijh % 4;
				a += cross(i - di[h], j - dj[h], i, j);
				imn = min(imn, i), imx = max(imx, i);
				ijh = nxt[ijh];
			}
			if (a < 0)
				ans += (long long) (imn + 1) * (n - imx);
		}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

raspad.c: In function 'main':
raspad.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
raspad.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39