Submission #727160

#	Time	Username	Problem	Language	Result	Execution time	Memory
727160		marvinthang	Mars (APIO22_mars)	C++17	36 / 100	187 ms	2868 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);
	if (i < m - 1 && j < m - 1) return h[0][0];
	string res(100, '0');
	vector <vector <char>> board(2 * n + 1, vector<char>(2 * n + 1, '0'));
	auto get_range = [&] (int i, int j, int k) {
		int m = 2 * (n - k - 1);
		int len = k + 2;
		int p = 2 * n - len + 1;
		if (k < 0) return make_pair(make_pair(i, i), make_pair(j, j));
		if (i < m - 1 && j < m - 1) return make_pair(make_pair(i, i), make_pair(j, j));
		if (i == m && j == m) return make_pair(make_pair(p, 2 * n), make_pair(p, 2 * n));
		if (i == m) return make_pair(make_pair(p, 2 * n), make_pair(j, j + len - 1));
		if (j == m) return make_pair(make_pair(i, i + len - 1), make_pair(p, 2 * n));
		if (i == m - 1) return make_pair(make_pair(i, i + len - 1), make_pair(j, j + len - 1));
		return make_pair(make_pair(i, i + len - 1), make_pair(j, j + len - 1));
	};
	REP(tx, 3) REP(ty, 3) {
		int cur = 0;
		auto p = get_range(i + tx, j + ty, k - 1);
		FORE(x, p.fi.fi, p.fi.se) FORE(y, p.se.fi, p.se.se) board[x][y] = h[tx][ty][cur++];
	}
	if (k == n - 1) {
		queue <pair <int, int>> q;
		int cnt = 0;
		REP(x, 2 * n + 1) REP(y, 2 * n + 1) if (board[x][y] == '1') {
			++cnt;
			board[x][y] = '0';
			q.emplace(x, y);
			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 > 2 * n || v > 2 * n || board[u][v] == '0') continue;
					board[u][v] = '0';
					q.emplace(u, v);
				}
			}
		}
		REP(i, 100) {
			res[i] = '0' + (cnt & 1);
			cnt >>= 1;
		}
		return res;
	}
	int cur = 0;
	auto p = get_range(i, j, k);
	FORE(x, p.fi.fi, p.fi.se) FORE(y, p.se.fi, p.se.se) res[cur++] = 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);

		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

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