Submission #578513

#	Time	Username	Problem	Language	Result	Execution time	Memory
578513		8e7	Mars (APIO22_mars)	C++17	100 / 100	1405 ms	4644 KiB

mars

//Challenge: Accepted
//#define _GLIBCXX_DEBUG 1
#include <bits/stdc++.h>
#include "mars.h"
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 85
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1<<30;

bool vis[3 * maxn];
int color[3 * maxn];
vector<int> adj[3 * maxn];

void dfs(int n, int c) {
	vis[n] = 1;
	color[n] = c;
	for (int v:adj[n]) {
		if (!vis[v]) dfs(v, c);
	}
}

std::string process(std::vector <std::vector<std::string>> a, int X, int Y, int k, int n) {
	int len = 2 * n + 1, m = len - 2 * k - 3;
	string ret = a[0][0];

	auto propagate = [&] (bool type) {
		if (type) {
			ret[1] = a[1][0][0];	
			for (int i = 2;i < 100;i++) ret[i] = a[2][0][i-2];
		} else {
			ret[1] = a[0][1][0];	
			for (int i = 2;i < 100;i++) ret[i] = a[0][2][i-2];
		}
	};
	if (X < m-1 && Y < m-1) {
		return ret;
	} else if (X < m && Y < m) {
		if (X == m - 1 && Y == m - 1) {
			int l = 1 + 2 * k;		
			string s;
			for (int i = 0;i < l;i++) s += a[2][1][i];
			reverse(s.begin(), s.end());
			s += a[1][1][0];
			for (int i = 0;i < l;i++) s += a[1][2][i];
			for (int i = 0;i < s.size();i++) ret[i] = s[i];
			ret[99] = a[0][0][0];
		} else {
			propagate(X == m-1);
		}
	} else if (X == m && Y == m) {

		for (int i = 0;i < 3 * maxn;i++) adj[i].clear(), vis[i] = 0, color[i] = 0;

		int l = 1 + 2 * k;	

		int cnt = 0; //the number of lone islands 
		for (int i = 83;i < 98;i++) cnt += (1<<(i-83)) * (a[2][2][i] - '0');
		string s, t, mid; // s is current row, t is row for previous iter

		if (k == 0) {
			s = a[2][0][0]; s += a[1][0][0];s += a[0][0][0];s += a[0][1][0];s += a[0][2][0];
			mid = a[2][1][0]; mid += a[1][1][0];mid += a[1][2][0];
			t = a[2][2][0];
		} else {
			for (int i = 0;i < l;i++) s += a[2][0][i];	
			reverse(s.begin(), s.end());
			s += a[1][0][0];
			s += a[0][0][0];
			s += a[0][1][0];
			for (int i = 0;i < l;i++) s += a[0][2][i];	

			for (int i = 0;i < l;i++) mid += a[2][1][i];
			reverse(mid.begin(), mid.end());
			mid += a[1][1][99];
			for (int i = 0;i < l;i++) mid += a[1][2][i];


			t += a[2][2][98];	
			for (int i = 0;i < 2 * (l - 2) + 1;i++) t += a[1][1][i];
			t += a[2][2][99];	
		}

		ret[98] = s[0];
		ret[99] = s.back();

		//parse component info for t	
		vector<int> comp(maxn, 0), last(maxn, -1);
		vector<int> seg;
		if (k > 0) {
			int cur = 0, prv = 0;
			for (char i:t) {
				if (i == '1' && prv == 0) cur++;
				if (i == '1') seg.push_back(cur);
				else seg.push_back(0);
				prv = i - '0';
			}	
			//cur is number of components
			stack<int> stk;
			for (int i = 0;i < 2 * cur;i += 2) {
				int type = (a[2][2][i] - '0') + (a[2][2][i+1] - '0') * 2;
				if (type == 0) comp[i/2+1] = i/2+1;
				else if (type == 1) {
					comp[i/2+1] = i/2+1;
					stk.push(i/2+1);
				} else if (type == 2) {
					comp[i/2+1] = stk.top();
					stk.pop();
				} else {
					comp[i/2+1] = stk.top();
				}
			}
		}
		//build graph
		auto addedge = [&] (int u, int v) {
			adj[u].push_back(v);
			adj[v].push_back(u);	
		};
		auto check = [&] (int u, int v, char c, char d) {
			if (c == '1' && d == '1') addedge(u, v);
		};
		if (k > 0) {
			for (int i = 0;i < t.size();i++) {
				if (t[i] == '1') {
					seg[i] = comp[seg[i]];		
					if (last[seg[i]] != -1) {
						addedge(i, last[seg[i]]);
					}
					last[seg[i]] = i;
				}
			}
		}
		for (int i = 0;i < l;i++) check(i, maxn+i, t[i], mid[i]);	
		for (int i = 0;i <= l;i++) check(maxn+i, 2*maxn+i, mid[i], s[i]);	
		for (int i = l-1;i < 2*l - 1;i++) check(i, maxn+i+2, t[i], mid[i+2]);	
		for (int i = l;i < 2*l + 1;i++) check(maxn+i, 2*maxn+i+2, mid[i], s[i+2]);	

		for (int i = 1;i < 2 * l+3;i++) {
			if (i < 2*l - 1) check(i-1, i, t[i-1], t[i]);	
			if (i < 2*l + 1) check(maxn + i-1, maxn + i, mid[i-1], mid[i]);	
			check(2*maxn + i-1, 2*maxn + i, s[i-1], s[i]);	
		}
		

		int upper = 0;
		{
			int cur = 0;
			for (int i = 0;i < 2 * l + 3;i++) {
				if (s[i] == '1' && !vis[2*maxn + i]) {
					cur++;
					dfs(2*maxn + i, cur);
				}
			}
			upper = cur;
		}
		
		for (int i = 0;i < 2 * l + 1;i++) {
			if (mid[i] == '1' && !vis[maxn + i]) {
				cnt++;
				dfs(maxn + i, 0);
			}
		}
		for (int i = 0;i < 2 * l - 1;i++) {
			if (t[i] == '1' && !vis[i]) {
				cnt++;
				dfs(i, 0);
			}
		}
		
		if (k == n-1) {
			upper += cnt;
			for (int i = 0;i < 100;i++) ret[i] = '0';
			for (int i = 0;i < 100;i++) ret[i] = '0';
			for (int i = 0;i < 20;i++) {
				ret[i] = ((upper>>i) & 1) + '0';
			}
			return ret;
		}
		//encodes component info
		{
			int prv = 0;
			vector<pii> vec;
			vector<int> st(maxn, inf), en(maxn, -1);
			for (int i = 0;i < 2 * l+3;i++) {
				if (s[i] == '1' && prv == 0) {
					int c = color[2*maxn+i];
					vec.push_back({c, i});
					st[c] = min(st[c], i);
					en[c] = max(en[c], i);
				}
				prv = s[i] - '0';
			}
			int idx = 0;
			for (auto [c, i]:vec) {
				if (i == st[c] && i == en[c]) {
					ret[idx] = '0', ret[idx+1] = '0';	
				} else if (i == st[c]) {
					ret[idx] = '1', ret[idx+1] = '0';
				} else if (i == en[c]) {
					ret[idx] = '0', ret[idx+1] = '1';
				} else {
					ret[idx] = '1', ret[idx+1] = '1';
				}
				idx += 2;
			}
		}
		
		//encodes cnt
		for (int i = 83;i < 98;i++) {
			ret[i] = ((cnt>>(i-83)) & 1) + '0';
		}

	} else {
		propagate(X == m);
	}
	return ret;
}

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:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    for (int i = 0;i < s.size();i++) ret[i] = s[i];
      |                   ~~^~~~~~~~~~
mars.cpp:137:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    for (int i = 0;i < t.size();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