Submission #588507

#	Time	Username	Problem	Language	Result	Execution time	Memory
588507		Joshc	Mars (APIO22_mars)	C++17	100 / 100	1326 ms	4808 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second
 
const int OFFSET = 1e6;
 
/*
00 = nothing
01 = left bracket
10 = rightbracket
11 = underscore
*/
 
string tobracket(int n, vector<vector<int>> comp) {
	// Given a list of components, generate the bracket sequence
	string res(100, '0');
	for (vector<int>& v : comp) {
		if (v.size() == 1) continue;
		res[2*v[0]+1] = '1';
		res[2*v.back()] = '1';
		for (int i=1; i+1<v.size(); i++) res[2*v[i]] = res[2*v[i]+1] = '1'; 
	}
	return res;
}
 
vector<vector<int>> tocomp(int n, string s) {
	// Given a bracket sequence, return the list of components
	vector<vector<int>> res, stack;
	for (int i=0; i<n; i++) {
		if (s[i*2] == '0' && s[i*2+1] == '0') res.push_back({i});
		else if (s[i*2] == '0' && s[i*2+1] == '1') stack.push_back({i});
		else if (s[i*2] == '1' && s[i*2+1] == '0') {
			stack.back().push_back(i);
			res.push_back(stack.back());
			stack.pop_back();
		} else stack.back().push_back(i);
	}
	return res;
}
 
vector<int> getblocks(string frontier) {
	// split the current frontier into blocks
	vector<int> res(frontier.size(), -1);
	int cur = -1;
	for (int i=0; i<frontier.size(); i++) {
		if (frontier[i] == '1') {
			if (!i || frontier[i-1] == '0') cur++;
			res[i] = cur;
		}
	}
	return res;
}
 
struct dsu {
	unordered_map<int, int> parent, sz;
	int comps = 0;
 
	int root(int x) {
		if (parent.find(x) == parent.end()) {
			sz[x] = 1;
			comps++;
			return parent[x] = x;
		}
		return x == parent[x] ? x : parent[x] = root(parent[x]);
	}
 
	void join(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return;
		comps--;
		if (sz[x] > sz[y]) swap(x, y);
		parent[x] = y;
		sz[y] += sz[x];
	}
 
	vector<vector<int>> getcomps() {
		vector<vector<int>> res;
		unordered_map<int, vector<int>> x;
		for (pii p : parent) x[root(p.f)].push_back(p.f);
		for (auto p : x) res.push_back(p.s);
		return res;
	}
};
 
vector<int> reduce(vector<int> v) {
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end())-v.begin());
	return v;
}
 
string process(vector<vector<string>> a, int i, int j, int k, int n) {
	string res(100, '0');
	if (i%2 == 0 && i && i >= j+1) {
		if (k == 0) {
			res[0] = a[0][0][0];
			res[1] = a[0][1][0];
			res[2] = a[1][0][0];
			res[3] = a[1][1][0];
			res[4] = a[2][0][0];
			res[5] = a[2][1][0];
		} else {
			for (int i=0; i<96; i++) res[i+4] = a[2][0][i];
			res[0] = a[0][0][0];
			res[1] = a[0][1][0];
			res[2] = a[1][0][0];
			res[3] = a[1][1][0];
		}
		return res;
	}
	if (j%2 == 0 && j && j >= i+1) {
		if (k == 0) {
			res[0] = a[0][0][0];
			res[1] = a[1][0][0];
			res[2] = a[0][1][0];
			res[3] = a[1][1][0];
			res[4] = a[0][2][0];
			res[5] = a[1][2][0];
		} else {
			for (int i=0; i<96; i++) res[i+4] = a[0][2][i];
			res[0] = a[0][0][0];
			res[1] = a[1][0][0];
			res[2] = a[0][1][0];
			res[3] = a[1][1][0];
		}
		return res;
	}
	if (i == 2*(n-k-1) && i == j) {
		if (k == 0) {
			string frontier;
			frontier += a[2][0][0];
			frontier += a[1][0][0];
			frontier += a[0][0][0];
			frontier += a[0][1][0];
			frontier += a[0][2][0];
			vector<int> blocks = getblocks(frontier);
			int x = *max_element(blocks.begin(), blocks.end())+1;
			unordered_map<int, int> pos = {{6, 0}, {3, 1}, {0, 2}, {1, 3}, {2, 4}};
			dsu d;
 
			for (int i=0; i<3; i++) {
				for (int j=0; j<3; j++) {
					if (a[i][j][0] == '1') d.root(i*3+j); // make sure node is considered
					if (i != 2 && a[i][j][0] == '1' && a[i+1][j][0] == '1') d.join(i*3+j, (i+1)*3+j);
					if (j != 2 && a[i][j][0] == '1' && a[i][j+1][0] == '1') d.join(i*3+j, i*3+j+1);
				}
			}
 
			vector<vector<int>> comps;
			for (vector<int>& comp : d.getcomps()) {
				vector<int> cur;
				for (int i : comp) {
					if (pos.find(i) != pos.end()) cur.push_back(blocks[pos[i]]);
				}
				if (cur.empty()) continue;
				comps.push_back(reduce(cur));
			}
 
			if (n == 1) {
				for (int i=0; i<10; i++) {
					if (d.comps&(1<<i)) res[i] = '1';
				}
				return res;
			}
 
			res = tobracket(x, comps);
			for (int i=0; i<10; i++) {
				if (d.comps&(1<<i)) res[i+90] = '1';
			}
			return res;
		}
 
 
		// for convenience, let's just fill in the entire bottom right square
		int sz = 2*n+1-i;
 
		vector<string> grid(sz, string(sz, '0'));
		grid[0][0] = a[0][0][0];
		grid[0][1] = a[0][1][0];
		grid[1][0] = a[1][0][0];
		grid[1][1] = a[1][1][0];
 
		for (int i=0; i<sz-2; i++) {
			grid[i+2][0] = a[2][0][i*2];
			grid[i+2][1] = a[2][0][i*2+1];
			grid[i+2][2] = a[2][1][i*2+1];
			grid[0][i+2] = a[0][2][i*2];
			grid[1][i+2] = a[0][2][i*2+1];
			grid[2][i+2] = a[1][2][i*2+1];
		}

		dsu d;
		vector<int> order;
		
		for (int i=2; i<sz; i++) {
			if (grid[i][2] == '1') d.root(i*100+2);
			if (grid[2][i] == '1') d.root(200+i);
		}
 
		string inner; // store the inner frontier
		for (int i=sz-1; i>1; i--) {
			inner += grid[i][2];
			order.push_back(i*100+2);
		}
		for (int i=3; i<sz; i++) {
			inner += grid[2][i];
			order.push_back(200+i);
		}
 
		for (int i=1; i<inner.size(); i++) {
			if (inner[i-1] == '1' && inner[i] == '1') d.join(order[i-1], order[i]);
		}
		
		vector<int> innerblocks = getblocks(inner);
		unordered_map<int, int> m;
		for (int i=0; i<innerblocks.size(); i++) m[innerblocks[i]] = order[i];

		int x = *max_element(innerblocks.begin(), innerblocks.end())+1;
		vector<vector<int>> innercomps = tocomp(x, a[2][2]);
		for (vector<int>& comp : innercomps) {
			for (int i : comp) d.join(m[comp[0]], m[i]);
		}
		
		d.comps = 0;
		for (int i=0; i<10; i++) {
			if (a[2][2][90+i] == '1') d.comps |= 1<<i;
		}
 
		for (int i=0; i<sz; i++) {
			for (int j=0; j<sz; j++) {
				if (grid[i][j] == '1') d.root(i*100+j);
			}
		}
 
		for (int i=0; i<sz; i++) {
			for (int j=0; j<sz; j++) {
				if (i+1 != sz && grid[i][j] == '1' && grid[i+1][j] == '1') d.join(i*100+j, (i+1)*100+j);
				if (j+1 != sz && grid[i][j] == '1' && grid[i][j+1] == '1') d.join(i*100+j, i*100+j+1);
			}
		}
		
		order.clear();
		string outer;
		unordered_map<int, int> pos;
		for (int i=sz-1; i>=0; i--) {
			pos[i*100] = outer.size();
			outer += grid[i][0];
		}
		for (int i=1; i<sz; i++) {
			pos[i] = outer.size();
			outer += grid[0][i];
		}
 
		vector<int> blocks = getblocks(outer);
 
		vector<vector<int>> comps;
		for (vector<int>& comp : d.getcomps()) {
			vector<int> cur;
			for (int i : comp) {
				if (pos.find(i) != pos.end()) cur.push_back(blocks[pos[i]]);
			}
			if (cur.empty()) continue;
			comps.push_back(reduce(cur));
		}
 
		if (k == n-1) {
			for (int i=0; i<10; i++) {
				if (d.comps&(1<<i)) res[i] = '1';
			}
			return res;
		}
		res = tobracket(x, comps);
		for (int i=0; i<10; i++) {
			if (d.comps&(1<<i)) res[i+90] = '1';
		}
		return res;
 
	}
	return a[0][0];
}

Compilation message (stderr)

mars.cpp: In function 'std::string tobracket(int, std::vector<std::vector<int> >)':
mars.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int i=1; i+1<v.size(); i++) res[2*v[i]] = res[2*v[i]+1] = '1';
      |                 ~~~^~~~~~~~~
mars.cpp: In function 'std::vector<int> getblocks(std::string)':
mars.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i=0; i<frontier.size(); i++) {
      |                ~^~~~~~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:215:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |   for (int i=1; i<inner.size(); i++) {
      |                 ~^~~~~~~~~~~~~
mars.cpp:221:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |   for (int i=0; i<innerblocks.size(); i++) m[innerblocks[i]] = order[i];
      |                 ~^~~~~~~~~~~~~~~~~~~

• 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