Submission #573696

#	Time	Username	Problem	Language	Result	Execution time	Memory
573696		teraqqq	Mars (APIO22_mars)	C++17	100 / 100	1449 ms	4964 KiB

mars

#include "mars.h"

#include <numeric>
#include <iostream>
#include <map>

using namespace std;
using pi = pair<int, int>;

struct Dsu {
	vector<int> p, c;

	Dsu (int n) : p(n), c(n, 1) {
		iota(p.begin(), p.end(), 0);
	}

	int root(int v) {
		return v == p[v] ? v : p[v] = root(p[v]);
	}

	bool unite(int a, int b) {
		a = root(a), b = root(b);
		if (a == b) {
			return false;
		} else {
			if (c[a] < c[b]) swap(a, b);
			p[b] = a;
			c[a] += c[b];
			return true;
		}
	}
};

vector<int> get_colors(vector<string> v, vector<int> info, int& additional_cost, vector<int>& slice, int& slice_diff) {
	const int n = v.size();
	Dsu dsu(n*n);

	vector<pi> bound;

	for (int i = n - 1; i >= 2; --i) bound.emplace_back(i, 2);
	for (int i = 3; i < n; ++i) bound.emplace_back(2, i);

	vector<int> st_colors;
	for (int i = 0; i < bound.size(); ++i) {
		auto [x, y] = bound[i];
		if (v[x][y] == '1') {
			if (info[i]) {
				st_colors.push_back(n*x + y);
			} else {
				dsu.unite(st_colors.back(), n*x+y);
			}
		} else {
			if (info[i]) st_colors.pop_back();
		}
	}

	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j) {
		if (v[i][j] != '1') continue;
		const int s = n*i + j;
		if (i + 1 < n && v[i+1][j] == '1') dsu.unite(s, s+n);
		if (j + 1 < n && v[i][j+1] == '1') dsu.unite(s, s+1);
	}

	vector<int> used(n*n);
	for (int i = 0; i < n; ++i) {
		if (v[0][i] == '1' && !used[dsu.root(i)])   used[dsu.root(i)]   = 1, ++slice_diff;
		if (v[i][0] == '1' && !used[dsu.root(i*n)]) used[dsu.root(i*n)] = 1, ++slice_diff;
	}

	for (int i = 1; i < n; ++i)
	for (int j = 1; j < n; ++j) {
		if (v[i][j] == '0') continue;
		int rt = dsu.root(n*i+j);
		if (!used[rt]) ++additional_cost;
		used[rt] = 1;
	}

	bound.clear();
	for (int i = n - 1; i >= 0; --i) bound.emplace_back(i, 0);
	for (int i = 1; i < n; ++i) bound.emplace_back(0, i);

	vector<int> res;
	for (auto [x, y] : bound) {
		res.push_back(dsu.root(n*x+y));
		slice.push_back(v[x][y] - '0');
	}
	return res;
}

void write_cost(string& res, int cost) {
	for (int i = 0; i < 11; ++i) {
		res[i+1] = (cost >> i) % 2 ? '1' : '0';
	}
}

string get_answer(int ans) {
	string res(100, '0');
	for (int i = 0; i < 20; ++i) {
		res[i] = '0' + (ans >> i) % 2;
	}
	return res;
}

int load_cost(string& res) {
	int cost = 0;
	for (int i = 0; i < 11; ++i) {
		cost += (res[i+1] - '0') << i;
	}
	return cost;
}

vector<int> get_mask_by_color(vector<int> cols, vector<int> slice) {
	const int n = cols.size();

	vector<int> res(n+1), st;

	for (int i = 0; i < n; ++i) {
		if (slice[i] == 0 || cols[i] == -1) continue;

		int last = i;
		for (int j = i + 1; j < n; ++j) {
			if (cols[j] == cols[i]) {
				cols[j] = -1;
				last = j;
			}
		}

		res[i] = 1;
		res[last+1] = 1;
	}

	return res;
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
	const vector<pi> dpos = { {-1,0}, {1,0}, {0,1}, {0,-1} };
	if (max(i, j) != 2 * (n-k-1)) return a[0][0];

	string res(100, '0');

	const int w = 2 * k + 3;

	if (max(i, j) == 2*n-2) {
		if (i == j) {
			vector<int> info { 1, 1 }, slice;
			vector v(3, string(3, '0'));
			for (int i = 3; i--; )
			for (int j = 3; j--; ) v[i][j] = a[i][j][0];

			int cost = 0, slice_diff = 0;
			auto cols = get_colors(v, info, cost, slice, slice_diff);
			auto info_write = get_mask_by_color(cols, slice);
			res[0] = a[0][0][0];
			write_cost(res, cost);
			for (int i = 0; i < info_write.size(); ++i) res[i+12] = info_write[i] + '0';

			if (i == 0) return get_answer(cost + slice_diff);
			return res;
		} else {
			if (i == 2*n-2 && j % 2 == 0) {
				res[0] = a[0][0][0];
				res[1] = a[1][0][0];
				res[2] = a[2][0][0];
				res[3] = a[0][1][0];
				res[4] = a[1][1][0];
				res[5] = a[2][1][0];
				return res;
			}

			if (j == 2*n-2 && i % 2 == 0) {
				res[0] = a[0][0][0];
				res[1] = a[0][1][0];
				res[2] = a[0][2][0];
				res[3] = a[1][0][0];
				res[4] = a[1][1][0];
				res[5] = a[1][2][0];
				return res;
			}

			if (i == 2*n-2 && j == 2*n-3) {
				res[0] = a[0][0][0];
				res[1] = a[0][1][0];
				res[2] = a[1][1][0];
				res[3] = a[2][1][0];
				return res;
			}

			if (i == 2*n-3 && j == 2*n-2) {
				res[0] = a[0][0][0];
				res[1] = a[1][0][0];
				res[2] = a[1][1][0];
				res[3] = a[1][2][0];
				return res;
			}
		}
	} else if (max(i, j) == 2*(n-k)-2) {
		if (i == j) {
			int cost = load_cost(a[2][2]);

			vector v(w, string(w, '0'));
			v[0][0] = a[0][0][0];
			v[0][1] = a[0][1][0];
			v[1][0] = a[1][0][0];
			v[1][1] = a[1][1][0];
			v[2][2] = a[2][2][0];

			const int W = w - 2;
			for (int i = 0; i < W; ++i) {
				v[i+2][0] = a[2][0][i];
				v[i+2][1] = a[2][0][i+W];
				v[0][i+2] = a[0][2][i];
				v[1][i+2] = a[0][2][i+W];
			}

			// cerr << a[2][1] << endl;

			for (int i = 0; i < W; ++i) {
				v[i+2][2] = a[2][1][i+1];
				v[2][2+i] = a[1][2][i+1];
			}

			vector<int> info(2*W), slice;
			for (int i = 0; i < 2*W; ++i) info[i] = a[2][2][i+12] - '0';

			int slice_cost = 0;
			auto cols = get_colors(v, info, cost, slice, slice_cost);
			auto info_write = get_mask_by_color(cols, slice);
			res[0] = a[0][0][0];
			write_cost(res, cost);
			for (int i = 0; i < info_write.size(); ++i) res[i+12] = info_write[i] + '0';
			if (i == 0) return get_answer(cost + slice_cost);
			return res;
		} else {
			if (i == 2*(n-k)-2 && j % 2 == 0) {
				res[0] = a[0][0][0];
				res[1] = a[1][0][0];
				for (int i = 2; i < w; ++i) {
					res[i] = a[2][0][i-2];
				}
				res[w]   = a[0][1][0];
				res[w+1] = a[1][1][0];
				for (int i = 2; i < w; ++i) {
					res[i+w] = a[2][0][i+w-4];
				}
				return res;
			}

			if (j == 2*(n-k)-2 && i % 2 == 0) {
				res[0] = a[0][0][0];
				res[1] = a[0][1][0];
				for (int i = 2; i < w; ++i) {
					res[i] = a[0][2][i-2];
				}
				res[w]   = a[1][0][0];
				res[w+1] = a[1][1][0];
				for (int i = 2; i < w; ++i) {
					res[i+w] = a[0][2][i+w-4];
				}
				return res;
			}

			if (i == 2*(n-k)-2 && j == 2*(n-k)-3) {
				res[0] = a[0][0][0];
				res[1] = a[0][1][0];
				res[2] = a[1][1][0];
				for (int i = 0; i < w-2; ++i) {
					res[i+3] = a[2][1][i];
				}
				return res;
			}

			if (j == 2*(n-k)-2 && i == 2*(n-k)-3) {
				res[0] = a[0][0][0];
				res[1] = a[1][0][0];
				res[2] = a[1][1][0];
				for (int i = 0; i < w-2; ++i) {
					res[i+3] = a[1][2][i];
				}
				return res;
			}
		}
	}

	return a[0][0];
}

Compilation message (stderr)

mars.cpp: In function 'std::vector<int> get_colors(std::vector<std::__cxx11::basic_string<char> >, std::vector<int>, int&, std::vector<int>&, int&)':
mars.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < bound.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |    for (int i = 0; i < info_write.size(); ++i) res[i+12] = info_write[i] + '0';
      |                    ~~^~~~~~~~~~~~~~~~~~~
mars.cpp:231:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |    for (int i = 0; i < info_write.size(); ++i) res[i+12] = info_write[i] + '0';
      |                    ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11