240382026-02-03 18:18:28algoproÚtépítéscpp17Wrong answer 0/100228ms3124 KiB
// UUID: bfacff29-1e1a-4ba1-af1f-2a7050d73f75
#include <bits/stdc++.h>
#include <random>
using namespace std;

int n, m;
mt19937 rnd;

int ti(int i, int j) {return i * (m + 1) + j;}
array<int, 2> tc(int c) {return {c / (m + 1), c % (m + 1)};}

bool scc(int c, vector<int> &p, vector<int> &vis, vector<vector<int>> &e) {
	vis[c] = true;
	for (int d : e[c]) {
		if (p[d] == -1 || (!vis[p[d]] && scc(p[d], p, vis, e))) {
			p[d] = c;
			return true;
		}
	}

	return false;
}


int main() {
	cin >> n >> m;
	vector<int> p((n + 1) * (m + 1), -1), vis((n + 1) * (m + 1));
	vector<vector<int>> e((n + 1) * (m + 1));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			if (c == '\\') {
				e[ti(i, j)].push_back(ti(i + 1, j + 1));
				e[ti(i + 1, j + 1)].push_back(ti(i, j));
			}

			if (c == '/') {
				e[ti(i + 1, j)].push_back(ti(i, j + 1));
				e[ti(i, j + 1)].push_back(ti(i + 1, j));
			}
		}
	}

	vector<int> ord;
	for (int i = 0; i < n + 1; i += 2) {
		for (int j = 0; j < m + 1; j++) {
			ord.push_back(ti(i, j));
		}
	}

	shuffle(ord.begin(), ord.end(), rnd);
	for (int c : ord) {
		vis.assign((n + 1) * (m + 1), false);
		scc(c, p, vis, e);
		cout<<c<<"\n";
	}

	vector<string> ans(n, string(m, '.'));
	int cnt = 0;
	for (int i = 1; i < n + 1; i += 2) {
		for (int j = 0; j < m + 1; j++) {
			if (p[ti(i, j)] == -1) continue;
			cnt++;
			auto x = tc(p[ti(i, j)]);
			if (x == array<int, 2> {i - 1, j - 1}) ans[i - 1][j - 1] = '\\';
			if (x == array<int, 2> {i + 1, j + 1}) ans[i][j] = '\\';
			if (x == array<int, 2> {i - 1, j + 1}) ans[i - 1][j] = '/';
			if (x == array<int, 2> {i + 1, j - 1}) ans[i][j - 1] = '/';
		}
	}

	cout << cnt << "\n";
	for (string line : ans) cout << line << "\n";
}
SubtaskSumTestVerdictTimeMemory
base0/100
1Wrong answer0/01ms316 KiB
2Wrong answer0/0134ms2868 KiB
3Wrong answer0/51ms316 KiB
4Wrong answer0/51ms316 KiB
5Wrong answer0/51ms316 KiB
6Wrong answer0/51ms316 KiB
7Wrong answer0/51ms316 KiB
8Wrong answer0/51ms316 KiB
9Wrong answer0/51ms316 KiB
10Wrong answer0/51ms316 KiB
11Wrong answer0/52ms564 KiB
12Wrong answer0/52ms564 KiB
13Wrong answer0/52ms784 KiB
14Wrong answer0/513ms820 KiB
15Wrong answer0/514ms868 KiB
16Wrong answer0/5130ms2784 KiB
17Wrong answer0/5130ms3064 KiB
18Wrong answer0/5228ms2704 KiB
19Wrong answer0/5129ms2612 KiB
20Wrong answer0/5138ms3124 KiB
21Wrong answer0/5133ms3076 KiB
22Wrong answer0/5128ms2356 KiB