Submission #236854

#	Time	Username	Problem	Language	Result	Execution time	Memory
236854		DanShaders	Tetris (COCI17_tetris)	C++17	80 / 80	5 ms	512 KiB

tetris

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

const int MAX_N = 11, INF = 0x3f3f3f3f;
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int n, m;
char a[MAX_N][MAX_N];

vector<pair<int, int>> pieces;

void dfs(int i, int j, char cc) {
	if (i < 0 || j < 0 || i >= n || j >= m || a[i][j] != cc)
		return;
	a[i][j] = '.';
	pieces.push_back({i, j});
	for (int d = 0; d < 4; ++d)
		dfs(i + dx[d], j + dy[d], cc);
}

int ans[5];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (a[i][j] != '.') {
				pieces.clear();
				dfs(i, j, a[i][j]);
				int minx = +INF, miny = +INF;
				int maxx = -1, maxy = -1;
				for (auto u : pieces) {
					minx = min(minx, u.x), miny = min(miny, u.y),
					maxx = max(maxx, u.x), maxy = max(maxy, u.y);
				}
				for (auto &u : pieces)
					u.x -= minx, u.y -= miny;
				maxx -= minx, maxy -= miny;
				if (maxx == 1 && maxy == 1) {
					++ans[0];
				} else if (maxx == 3 || maxy == 3) {
					++ans[1];
				} else {
					vector<pair<int, int>> freep;
					for (int cx = 0; cx <= maxx; ++cx) {
						for (int cy = 0; cy <= maxy; ++cy) {
							bool flag = false;
							for (auto u : pieces)
								if (pair<int, int>{cx, cy} == u)
									flag = true;
							if (!flag)
								freep.push_back({cx, cy});
						}
					}
					if (freep[0].x == freep[1].x || freep[0].y == freep[1].y)
						++ans[4];
					else {
						++ans[2 + ((freep[0].y == 0) ^ (maxx != 2))];
					}
				}
			}
		}
	}
	for (int i = 0; i < 5; ++i)
		cout << ans[i] << "\n";
	return 0;
}

• Subtask 1: 80 / 80