Submission #22583

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22583	2017-04-30T05:44:15 Z	- - - - - - - List of honorable mention follows - - - - - - -(#999, xhae, ainu7, littlesheep)	Young Zebra (KRIII5_YZ)	C++14	0 / 7	500 ms	147856 KB

YZ

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int r, c;
vector<string> data;

vector<vector<int>> getCnt(vector<string> &field) {	
	int r = field.size(), c = field[0].size();
	vector<vector<int>> ret(r, vector<int>(c, -1));
	for(int i= 0; i < r; i++)
		for(int j= 0; j< c;j++) {
			if(ret[i][j] != -1) continue;
			ret[i][j] = 0;
			queue<tuple<int, int>> q;
			q.push(make_tuple(i, j));
			int cnt = 0;

			vector<tuple<int, int>> coords;
			while(!q.empty()) {
				cnt++;
				int y, x;
				tie(y, x) = q.front();
				coords.emplace_back(y, x);
				q.pop();

				const int mov[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
				for(int k = 0; k < 4; k++) {
					int ny = y + mov[k][0];
					int nx = x + mov[k][1];
					if(ny >= 0 and ny < r and nx >= 0 and nx < c and 
						ret[ny][nx] == -1 and field[ny][nx] == field[y][x]) {
						ret[ny][nx] = 0;
						q.push(make_tuple(ny, nx));
					}
				}
			}

			for(auto coord: coords) {
				int y, x;
				tie(y, x) = coord;
				ret[y][x] = cnt;
			}
		}
	return ret;
}

int main(void) {
	cin >> r >> c;
	data = vector<string>(r);
	for(int i =0 ; i <r; i++) cin >> data[i];

	vector<string> smallf(r * 3);
	vector<string> largef(r * 7);

	for(int i = 0; i < 3 * r; i++)
		for(int j = 0; j < 3; j++)
			smallf[i] += data[i % r];
	for(int i =0 ; i < 7 * r; i++)
		for(int j = 0; j < 7; j++)
			largef[i] += data[i % r];

	auto scnt = getCnt(smallf);
	auto lcnt = getCnt(largef);

	for(int i =0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			int v = -2;
			for(int q = 1; q <= 5; q++) {
				for(int w = 1; w <= 5; w++) {
					if(scnt[i + r][j + c] != lcnt[i + r * q][j + c * w]) {
						v = -1;
						break;
					} else {
						if(v == -2) v = scnt[i + r][j + c];
						else if(v != scnt[i + r][j + c]) {
							v = -1;
							break;
						}
					}
				}
				if(v == -1) break;
			}

			cout << v << " ";
		}
		cout << "\n";
	}

	return 0;
}

Subtask #1

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	489 ms	57732 KB	Output is correct
2	Execution timed out	500 ms	147856 KB	Execution timed out
3	Halted	0 ms	0 KB	-