Submission #575934

#	Time	Username	Problem	Language	Result	Execution time	Memory
575934		SHZhang	Mars (APIO22_mars)	C++17	100 / 100	1620 ms	4808 KiB

mars

#include "mars.h"
#include <utility>
#include <set>

using namespace std;

// on phase k, preexisting size 2 * k + 1
// row,  col
// even, even: comp # (11 bits), bot up, bot down, right left, right right,
// perimeter blocks (up to 80)
// even, odd: bottom region, first top row, then bottom row
// odd, even: right region, first left col, then right col

#define encode(r, c) ((r) * (2 * k + 3) + (c))

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

int fin(int* uf, int x)
{
	if (uf[x] == x) return x;
	return uf[x] = fin(uf, uf[x]);
}

void un(int* uf, int x, int y)
{
	x = fin(uf, x);
	y = fin(uf, y);
	uf[x] = y;
}

string process(vector <vector<string>> a, int x, int y, int k, int n)
{
	(void)n;
	string ans = string(100, '0');
	if (x % 2 == 1 && y % 2 == 1) return ans;
	if (k == 0) {
		if (x % 2 == 0 && y % 2 == 1) {
			ans[0] = a[1][0][0];
			ans[1] = a[1][1][0];
			ans[2] = a[2][0][0];
			ans[3] = a[2][1][0];
		} else if (x % 2 == 1 && y % 2 == 0) {
			ans[0] = a[0][1][0];
			ans[1] = a[1][1][0];
			ans[2] = a[0][2][0];
			ans[3] = a[1][2][0];
		} else {
			ans[11] = a[1][0][0];
			ans[12] = a[2][0][0];
			ans[13] = a[0][1][0];
			ans[14] = a[0][2][0];
			ans[96] = a[1][1][0];
			ans[97] = a[1][2][0];
			ans[98] = a[2][1][0];
			ans[99] = a[2][2][0];
			int uf[9];
			for (int i = 0; i < 9; i++) uf[i] = i;
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					if (a[i][j][0] == '0') continue;
					for (int d = 0; d < 4; d++) {
						int ni = i + dx[d];
						int nj = j + dy[d];
						if (ni < 0 || ni >= 3 || nj < 0 || nj >= 3) continue;
						if (a[ni][nj][0] == '1') {
							//if (x == 0 && y == 0) printf("! %d %d %d %d\n", i, j, ni, nj);
							un(uf, encode(i, j), encode(ni, nj));
						}
					}
				}
			}
			int compcnt = 0;
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					if (a[i][j][0] == '0') continue;
					if (fin(uf, encode(i, j)) == encode(i, j)) compcnt++;
				}
			}
			for (int i = 0; i < 11; i++) {
				if (compcnt & (1 << i)) {
					ans[i] = '1';
				} else {
					ans[i] = '0';
				}
			}
			vector<pair<int, int> > botright1;
			for (int i = 0; i <= 2; i++) botright1.push_back(make_pair(2, i));
			for (int i = 1; i >= 0; i--) botright1.push_back(make_pair(i, 2));
			vector<int> botright;
			for (int i = 0; i < botright1.size(); i++) {
				if (a[botright1[i].first][botright1[i].second][0] == '1' &&
					(i == 0 || a[botright1[i-1].first][botright1[i-1].second][0] == '0')) {
					botright.push_back(encode(botright1[i].first, botright1[i].second));
				}
			}
			for (int i = 0; i < botright.size(); i++) {
				bool has_before = false;
				bool has_after = false;
				for (int j = 0; j < i; j++) {
					if (x == 0 && y == 0) {
						//fprintf(stderr, "??? %d %d\n", botright[i], botright[j]);
					}
					if (fin(uf, botright[i]) == fin(uf, botright[j])) has_before = true;
				}
				for (int j = i + 1; j < botright.size(); j++) {
					if (fin(uf, botright[i]) == fin(uf, botright[j])) has_after = true;
				}
				if (!has_before && !has_after) {
					//if (x == 0 && y == 0) fprintf(stderr, "only\n");
					ans[15 + 2*i] = '0';
					ans[16 + 2*i] = '0';
				} else if (has_before && !has_after) {
					// last
					//if (x == 0 && y == 0) fprintf(stderr, "last\n");
					ans[15 + 2*i] = '1';
					ans[16 + 2*i] = '1';
				} else if (!has_before && has_after) {
					// first
					//if (x == 0 && y == 0) fprintf(stderr, "first\n");
					ans[15 + 2*i] = '0';
					ans[16 + 2*i] = '1';
				} else {
					//if (x == 0 && y == 0) fprintf(stderr, "middle\n");
					ans[15 + 2*i] = '1';
					ans[16 + 2*i] = '0';
				}
			}
		}
		if (k == n - 1) {
			for (int i = 11; i < 100; i++) ans[i] = '0';
		}
		return ans;
	}
	if (x % 2 == 0 && y % 2 == 1) {
		for (int i = 0; i < 2 * k; i++) {
			ans[i] = a[2][0][i];
			ans[i + 2*k + 2] = a[2][0][2*k+i];
		}
		for (int i = 0; i < 2 * k; i++) {
			ans[i + 2] = a[2][2][i];
			ans[i + 2*k + 4] = a[2][2][2*k+i];
		}
	} else if (x % 2 == 1 && y % 2 == 0) {
		for (int i = 0; i < 2 * k; i++) {
			ans[i] = a[0][2][i];
			ans[i + 2*k + 2] = a[0][2][2*k+i];
		}
		for (int i = 0; i < 2 * k; i++) {
			ans[i + 2] = a[2][2][i];
			ans[i + 2*k + 4] = a[2][2][2*k+i];
		}
	} else {
		int* uf = new int[(2 * k + 3) * (2 * k + 3)];
		bool* outer_comp = new bool[(2 * k + 3) * (2 * k + 3)];
		for (int i = 0; i < (2 * k + 3) * (2 * k + 3); i++) {
			uf[i] = i; outer_comp[i] = true;
		}
		bool* land[45];
		for (int i = 0; i < 45; i++) {
			land[i] = new bool[45];
		}
		for (int i = 0; i < (2 * k + 3); i++) {
			for (int j = 0; j < (2 * k + 3); j++) {
				land[i][j] = false;
			}
		}
		for (int i = 0; i < 2 * k; i++) {
			land[2 * k - 1][i + 1] = (a[0][1][i] == '1');
			land[2 * k][i + 1] = (a[0][1][2 * k + i] == '1');
			land[2 * k + 1][i + 1] = (a[2][1][i] == '1');
			land[2 * k + 2][i + 1] = (a[2][1][2 * k + i] == '1');
			land[i + 1][2 * k - 1] = (a[1][0][i] == '1');
			land[i + 1][2 * k] = (a[1][0][2 * k + i] == '1');
			land[i + 1][2 * k + 1] = (a[1][2][i] == '1');
			land[i + 1][2 * k + 2] = (a[1][2][2 * k + i] == '1');
		}
		//fprintf(stderr, "! %d %c %c %c %c\n", k, a[0][0][11], a[0][0][12], a[0][0][13], a[0][0][14]);
		land[2 * k - 1][0] = (a[0][0][11] == '1');
		land[2 * k][0] = (a[0][0][12] == '1');
		land[2 * k + 1][0] = (a[2][0][11] == '1');
		land[2 * k + 2][0] = (a[2][0][12] == '1');
		land[0][2 * k - 1] = (a[0][0][13] == '1');
		land[0][2 * k] = (a[0][0][14] == '1');
		land[0][2 * k + 1] = (a[0][2][13] == '1');
		land[0][2 * k + 2] = (a[0][2][14] == '1');
		land[2 * k + 1][2 * k + 1] = (a[2][2][96] == '1');
		land[2 * k + 1][2 * k + 2] = (a[2][2][97] == '1');
		land[2 * k + 2][2 * k + 1] = (a[2][2][98] == '1');
		land[2 * k + 2][2 * k + 2] = (a[2][2][99] == '1');
		//fprintf(stderr, "%d %d %d\n", x, y, k);
		for (int i = 0; i <= 2 * k + 2; i++) {
			for (int j = 0; j <= 2 * k + 2; j++) {
				//fprintf(stderr, "%d", (int)land[i][j]);
			}
			//fprintf(stderr, "\n");
		}
		ans[11] = a[2][0][11];
		ans[12] = a[2][0][12];
		ans[13] = a[0][2][13];
		ans[14] = a[0][2][14];
		ans[96] = a[2][2][96];
		ans[97] = a[2][2][97];
		ans[98] = a[2][2][98];
		ans[99] = a[2][2][99];
		vector<pair<int, int> > botright1;
		for (int i = 0; i <= 2 * k; i++) botright1.push_back(make_pair(2 * k, i));
		for (int i = 2 * k - 1; i >= 0; i--) botright1.push_back(make_pair(i, 2 * k));
		vector<int> botright;
		for (int i = 0; i < botright1.size(); i++) {
			if (land[botright1[i].first][botright1[i].second] &&
				(i == 0 || !land[botright1[i-1].first][botright1[i-1].second])) {
					//fprintf(stderr, "! %d %d\n", botright1[i].first, botright1[i].second);
				botright.push_back(encode(botright1[i].first, botright1[i].second));
			}
		}
		vector<int> stk;
		for (int i = 0; i < botright.size(); i++) {
			if (a[0][0][15 + 2*i] == '0' && a[0][0][16 + 2*i] == '0') {
				// only element in comp
				//fprintf(stderr, "only\n");
			} else if (a[0][0][15 + 2*i] == '0' && a[0][0][16 + 2*i] == '1') {
				// first element in comp
				stk.push_back(botright[i]);
				//fprintf(stderr, "first\n");
			} else if (a[0][0][15 + 2*i] == '1' && a[0][0][16 + 2*i] == '0') {
				// middle element in comp
				un(uf, stk.back(), botright[i]);
				//fprintf(stderr, "middle\n");
			} else if (a[0][0][15 + 2*i] == '1' && a[0][0][16 + 2*i] == '1') {
				// last element in comp
				//fprintf(stderr, "last\n");
				un(uf, stk.back(), botright[i]);
				stk.pop_back();
			}
		}
		for (int i = 0; i < 2 * k + 1; i++) {
			for (int j = 0; j < 2 * k + 1; j++) {
				if (!land[i][j]) continue;
				for (int d = 0; d < 4; d++) {
					int ni = i + dx[d];
					int nj = j + dy[d];
					if (ni < 0 || ni >= 2 * k + 1 || nj < 0 || nj >= 2 * k + 1) continue;
					if (land[ni][nj]) un(uf, encode(i, j), encode(ni, nj));
				}
			}
		}
		set<int> old_bound_comps;
		for (int i = 0; i < botright.size(); i++) {
			old_bound_comps.insert(fin(uf, botright[i]));
		}
		for (int i = 0; i < 2 * k + 3; i++) {
			for (int j = 0; j < 2 * k + 3; j++) {
				if (!land[i][j]) continue;
				for (int d = 0; d < 4; d++) {
					int ni = i + dx[d];
					int nj = j + dy[d];
					if (ni < 0 || ni >= 2 * k + 3 || nj < 0 || nj >= 2 * k + 3) continue;
					if (land[ni][nj]) un(uf, encode(i, j), encode(ni, nj));
				}
			}
		}
		set<int> new_bound_comps;
		for (int i = 0; i < botright.size(); i++) {
			new_bound_comps.insert(fin(uf, botright[i]));
		}
		int compcnt = (int)new_bound_comps.size() - (int)old_bound_comps.size();
		//fprintf(stderr, "1 %d %d\n", (int)new_bound_comps.size(), (int)old_bound_comps.size());
		for (int i = 0; i < 11; i++) {
			if (a[0][0][i] == '1') compcnt += (1 << i);
		}
		for (int i = 0; i < 2 * k + 1; i++) {
			for (int j = 0; j < 2 * k + 1; j++) {
				if (!land[i][j]) continue;
				outer_comp[fin(uf, encode(i, j))] = false;
			}
		}
		for (int i = 0; i < 2 * k + 3; i++) {
			for (int j = 0; j < 2 * k + 3; j++) {
				if (!land[i][j]) continue;
				if (fin(uf, encode(i, j)) == encode(i, j) && outer_comp[encode(i, j)]) compcnt++;
			}
		}
		for (int i = 0; i < 11; i++) {
			if (compcnt & (1 << i)) {
				ans[i] = '1';
			} else {
				ans[i] = '0';
			}
		}
		botright1.clear();
		for (int i = 0; i <= 2 * k + 2; i++) botright1.push_back(make_pair(2 * k + 2, i));
		for (int i = 2 * k + 1; i >= 0; i--) botright1.push_back(make_pair(i, 2 * k + 2));
		botright.clear();
		for (int i = 0; i < botright1.size(); i++) {
			if (land[botright1[i].first][botright1[i].second] &&
				(i == 0 || !land[botright1[i-1].first][botright1[i-1].second])) {
				botright.push_back(encode(botright1[i].first, botright1[i].second));
			}
		}
		for (int i = 0; i < botright.size(); i++) {
			bool has_before = false;
			bool has_after = false;
			for (int j = 0; j < i; j++) {
				if (fin(uf, botright[i]) == fin(uf, botright[j])) has_before = true;
			}
			for (int j = i + 1; j < botright.size(); j++) {
				if (fin(uf, botright[i]) == fin(uf, botright[j])) has_after = true;
			}
			if (!has_before && !has_after) {
				ans[15 + 2*i] = '0';
				ans[16 + 2*i] = '0';
			} else if (has_before && !has_after) {
				// last
				ans[15 + 2*i] = '1';
				ans[16 + 2*i] = '1';
			} else if (!has_before && has_after) {
				// first
				ans[15 + 2*i] = '0';
				ans[16 + 2*i] = '1';
			} else {
				ans[15 + 2*i] = '1';
				ans[16 + 2*i] = '0';
			}
		}
		//fprintf(stderr, "! %d\n", compcnt);
		delete[] uf;
		delete[] outer_comp;
		for (int i = 0; i < 45; i++) {
			delete[] land[i];
		}
	}
	if (k == n - 1) {
		for (int i = 11; i < 100; i++) ans[i] = '0';
	}
	return ans;
}

Compilation message (stderr)

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    for (int i = 0; i < botright1.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
mars.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for (int i = 0; i < botright.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
mars.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int j = i + 1; j < botright.size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
mars.cpp:210:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |   for (int i = 0; i < botright1.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:218:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |   for (int i = 0; i < botright.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
mars.cpp:249:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |   for (int i = 0; i < botright.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
mars.cpp:264:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  264 |   for (int i = 0; i < botright.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
mars.cpp:295:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  295 |   for (int i = 0; i < botright1.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
mars.cpp:301:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  301 |   for (int i = 0; i < botright.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
mars.cpp:307:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  307 |    for (int j = i + 1; j < botright.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~

• 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