Submission #798939

#	Time	Username	Problem	Language	Result	Execution time	Memory
798939		marvinthang	Mars (APIO22_mars)	C++17	54 / 100	382 ms	4436 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);
	string res(100, '0');
	vector <vector <char>> board(2 * n + 1, vector<char>(2 * n + 1, '0'));
	auto get_first = [&] (int i, int k) {
		return min(max(i, i * (2 * n + 1) / 3), 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 - 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;
	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';
		}
 
		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:50:6: warning: unused variable 'm' [-Wunused-variable]
   50 |  int m = 2 * (n - k - 1);
      |      ^
mars.cpp:87:6: warning: unused variable 'cur' [-Wunused-variable]
   87 |  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: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11