Submission #799098

#	Time	Username	Problem	Language	Result	Execution time	Memory
799098		marvinthang	Mars (APIO22_mars)	C++17	100 / 100	1874 ms	5408 KiB

mars

/*************************************
*    author: marvinthang             *
*    created: 20.04.2023 11:09:59    *
*************************************/
 
#include "mars.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif
 
template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
 
// end of template
 
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
 
string process(vector <vector <string>> h, int i, int j, int k, int n) {
	int m = 2 * (n - k - 1);
	int sz = 2 * n + 1;
	string res(100, '0');
	vector board(sz, vector<char>(sz, '0'));
	vector comps(sz, vector<int>(sz));
	vector adj(sz, vector(sz, vector<pair<int, int>>()));

	auto bfs = [&] (int sx, int sy, int cl) {
		queue <pair <int, int>> q;
		q.emplace(sx, sy);
		comps[sx][sy] = cl;
		while (!q.empty()) {
			auto [x, y] = q.front(); q.pop();
			REP(d, 4) {
				int u = x + dx[d];
				int v = y + dy[d];
				if (u < 0 || v < 0 || u >= sz || v >= sz || board[u][v] == '0' || comps[u][v]) continue;
				comps[u][v] = cl;
				q.emplace(u, v);
			}
			for (auto [u, v]: adj[x][y]) {
				if (board[u][v] == '0' || comps[u][v]) continue;
				comps[u][v] = cl;
				q.emplace(u, v);
			}
		}
	};

	auto toBinary = [&] (int v, int len) {
		string res;
		REP(i, len) {
			res += '0' + (v & 1);
			v >>= 1;
		};
		return res;
	};
	auto toDecimal = [&] (const string &s, int l, int len) {
		int res = 0;
		FORD(i, l + len, l) res = res << 1 | (s[i] == '1');
		return res;
	};
	auto getBorder = [&] (int i, int j) {
		vector <pair <int, int>> res;
		if (!i) {
			if (!j) {
				REP(i, n + 1) res.emplace_back(n, i);
				REPD(i, n) res.emplace_back(i, n);
			} else {
				FORD(i, sz, n) res.emplace_back(n, i);
				REPD(i, n) res.emplace_back(i, n);
			}
		} else {
			if (!j) {
				REP(i, n) res.emplace_back(n, i);
				FOR(i, n, sz) res.emplace_back(i, n);
			} else {
				FORD(i, sz, n) res.emplace_back(n, i);
				FOR(i, n + 1, sz) res.emplace_back(i, n);
			}
		}
		return res;
	};

	if (n == 1) {
		int cl = 0;
		REP(x, sz) REP(y, sz) board[x][y] = h[x][y][0];
		REP(x, sz) REP(y, sz) if (board[x][y] == '1' && !comps[x][y]) {
			++cl;
			bfs(x, y, cl);
		}
		return toBinary(cl, 100);
	}

	if (k == n - 1) {
		int res = 0;
		for (int i: {0, 2}) for (int j: {0, 2}) {
			res += toDecimal(h[i][j], 83, 17);
			vector border(getBorder(i, j));
			string mask = h[i][j].substr(0, 41);
			vector <int> head;
			REP(i, border.size()) {
				auto [x, y] = border[i];
				if (mask[i] == '1') {
					board[x][y] = '1';
					if (!i || mask[i - 1] == '0') head.push_back(i);
				}
			}
			string open(h[i][j].substr(41, 21)), close(h[i][j].substr(62, 21));
			stack <pair <int, int>> st;
			REP(i, head.size()) {
				int p = head[i];
				auto [x, y] = border[p];
				if (open[i] == '1') st.emplace(x, y);
				else {
					auto [u, v] = st.top();
					adj[x][y].emplace_back(u, v);
					adj[u][v].emplace_back(x, y);
				}
				if (close[i] == '1') st.pop();
			}
		}
		REP(x, sz) REP(y, sz) if (board[x][y] == '1' && !comps[x][y]) {
			++res;
			bfs(x, y, res);
		}
		return toBinary(res, 100);
	}

	auto get_first = [&] (int i, int k) {
		if (k == n - 1) return !i ? 0 : i == 1 ? n + 1 : i == 2 ? n : sz;
		return min(max(i, i * n / 2), i + 2 * k);
	};

	int li = get_first(i, k + 1), lj = get_first(j, k + 1);
	int ri = get_first(i + 1, k + 1), rj = get_first(j + 1, k + 1);
	REP(tx, 3) REP(ty, 3) {
		int lx = get_first(i + tx, k), ly = get_first(j + ty, k);
		int rx = get_first(i + tx + 1, k), ry = get_first(j + ty + 1, k);
		FOR(x, lx, rx) FOR(y, ly, ry) board[x][y] = h[tx][ty][(x - lx) * 10 + (y - ly)];
	}

	if (k == n - 2) {
		if (i & 1 || j & 1) return res;
		REP(x, sz) REP(y, sz) if (x < li || x >= ri || y < lj || y >= rj) board[x][y] = '0';
		vector border(getBorder(i, j));
		int cl = 0;
		for (auto [x, y]: border) if (board[x][y] == '1' && !comps[x][y]) {
			++cl;
			bfs(x, y, cl);
		}
		int res = 0;
		FOR(x, li, ri) FOR(y, lj, rj) if (board[x][y] == '1' && !comps[x][y]) {
			++res;
			bfs(x, y, res);
		}
		bool first = true;
		string mask(41, '0');
		vector <int> head;
		REP(i, border.size()) {
			auto [x, y] = border[i];
			if (board[x][y] == '1') {
				mask[i] = '1';
				if (!i || board[border[i - 1].fi][border[i - 1].se] == '0') head.push_back(i);
			}
		}
		string open(21, '0'), close(21, '0');
		vector <bool> used(cl + 1);
		REP(i, head.size()) {
			int p = head[i];
			auto [x, y] = border[p];
			if (!used[comps[x][y]]) {
				used[comps[x][y]] = true;
				open[i] = '1';
			}
		}
		REPD(i, head.size()) {
			int p = head[i];
			auto [x, y] = border[p];
			if (used[comps[x][y]]) {
				used[comps[x][y]] = false;
				close[i] = '1';
			}
		}
		return mask + open + close + toBinary(res, 17);
	}

	int cur = 0;
	FOR(x, li, ri) FOR(y, lj, rj) res[(x - li) * 10 + (y - lj)] = board[x][y];
	return res;
}
 
#ifdef LOCAL
#include "mars.h"
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <string>
#include <bitset>
 
using namespace std;
 
static void WA(string msg)
{
	cout << "WA: " << msg << endl;
	exit(0);
}
 
static long long to_longlong(string s)
{
  long long ans=0;
  for(int i=(int)s.size()-1;i>=0;i--)
    ans=(ans*2)+s[i]-'0';
  return ans;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	file("mars");
	int t;
	assert(scanf("%d",&t) == 1);
	while(t--)
	{
		int n;
		assert(scanf("%d",&n) == 1);
 
		vector <vector<char>> s(2*n+1, vector<char>(2*n+1));
		for(int i = 0; i < 2*n+1; i++) {
			for(int j = 0; j < 2*n+1; j++) {
				assert(scanf(" %c",&s[i][j]) == 1);
				// cout << s[i][j] << ' ';
			}
			// cout << '\n';
		}
		// cout << string(10, '=') << '\n';
 
		vector <vector<string>> h(2*n+1, vector<string>(2*n+1, string(100 ,'0')));
		for(int i = 0; i < 2*n+1; i++)
			for(int j = 0; j < 2*n+1; j++)
				h[i][j][0] = s[i][j];
 
		vector <vector<string>> subarr(3, vector<string>(3));
		for(int k = 0; k < n; k++)
		{
			int m = 2*(n-k-1);
			for(int i = 0; i <= m; i++)
			{
				for(int j = 0; j <= m; j++)
				{
					for(int y = 0; y < 3; y++)
					{
						for(int x = 0; x < 3; x++)
						{
							subarr[y][x] = h[i+y][j+x];
						}
					}
					h[i][j] = process(subarr, i, j, k, n);
 
					if(h[i][j].size() != 100) WA("Invalid return length");
					for(int l = 0; l < 100; l++)
						if(h[i][j][l] != '0' && h[i][j][l] != '1') WA("Invalid return");
				}
			}
		}
		cout << to_longlong(h[0][0]) << '\n';
	}
}
#endif

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:185:8: warning: unused variable 'first' [-Wunused-variable]
  185 |   bool first = true;
      |        ^~~~~
mars.cpp:50:6: warning: unused variable 'm' [-Wunused-variable]
   50 |  int m = 2 * (n - k - 1);
      |      ^
mars.cpp:216:6: warning: unused variable 'cur' [-Wunused-variable]
  216 |  int cur = 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