Submission #22390

#	Time	Username	Problem	Language	Result	Execution time	Memory
22390		2000/4000 (#40)	Young Zebra (KRIII5_YZ)	C++14	7 / 7	36 ms	5284 KiB

YZ

#include <cstdio>
#include <tuple>
#include <deque>

using namespace std;

const int MAXN = 404;
typedef tuple<bool,int,int> ii;

int N, M;
bool D[MAXN][MAXN];
int ans[MAXN][MAXN];
int sz[MAXN * MAXN];
ii visited[MAXN][MAXN];
char imsi[MAXN];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

tuple<int,int> clear_div(int x, int y) {
	if (x < 0) {
		const int d = (-x) / y; 
		const int r = (-x) % y;
		if (r == 0) return make_tuple(-d, 0);
		else return make_tuple(-(d + 1), y - r);
	}
	return make_tuple(x / y, x % y);
}

int main() {
	// 1. input
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%s", imsi);
		for (int j = 0; j < M; ++j) {
			D[i][j] = (imsi[j] == 'B');
		}
	}

	// 2. process
	deque<tuple<int, int>> Q;
	int cnt = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			if (ans[i][j]) continue;
			bool color = D[i][j];
			bool inf = false;
			Q.clear();

			Q.emplace_back(i, j);
			visited[i][j] = make_tuple(true, 0, 0);
			while(!Q.empty()) {
				const int p = get<0>(Q.front());
				const int q = get<1>(Q.front());
				Q.pop_front();
				++sz[cnt];

				int pr, qr, pd, qd;
				tie(pd, pr) = clear_div(p, N);
				tie(qd, qr) = clear_div(q, M);
				ans[pr][qr] = cnt;

				for (int k = 0; k < 4; ++k) {
					int xpr, xqr, xpd, xqd;
					tie(xpd, xpr) = clear_div(p + dx[k], N);
					tie(xqd, xqr) = clear_div(q + dy[k], M);

					if (D[xpr][xqr] != color) continue;
					else if (get<0>(visited[xpr][xqr])) {
						if (xpd == get<1>(visited[xpr][xqr])\
							&& xqd == get<2>(visited[xpr][xqr])) {
							continue;
						} else {
							// problem!
							inf = true;
						}
					} else {
						visited[xpr][xqr] = make_tuple(true, xpd, xqd);
						Q.emplace_back(p + dx[k], q + dy[k]);
					}
				}
			}

			if (inf) sz[cnt] = -1;
			++cnt;
		}
	}

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			printf("%d ", sz[ans[i][j]]);
		}
		puts("");
	}

	return 0;
}

Compilation message (stderr)

YZ.cpp: In function 'int main()':
YZ.cpp:31:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
                        ^
YZ.cpp:33:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", imsi);
                    ^

• Subtask 1: 7 / 7