oj.uz

Submission #727152

# Submission time Handle Problem Language Result Execution time Memory
727152 2023-04-20T05:47:04 Z marvinthang Mars (APIO22_mars) C++17
14 / 100
 17 ms 2172 KB 
/*************************************
*    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);
	vector <vector <char>> board(2 * n + 1, vector<char>(2 * n + 1, '0'));
	// cerr << i << ' ' << j << ' ' << k << '\n';
	REP(tx, 3) REP(ty, 3) {
		int cur = 0;
		FORE(x, i + tx, 2 * n) FORE(y, j + ty, 2 * n) board[x][y] = h[tx][ty][cur++];
	}
	// REP(i, 2 * n + 1) REP(j, 2 * n + 1) cout << board[i][j] << " \n"[j == 2 * n];
	string res(100, '0');
	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;
	FORE(x, i, 2 * n) FORE(y, j, 2 * n) 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1984 KB Output is correct
2 Correct 8 ms 2064 KB Output is correct
3 Correct 8 ms 2068 KB Output is correct
4 Correct 8 ms 1980 KB Output is correct
5 Correct 8 ms 1928 KB Output is correct
6 Correct 8 ms 1956 KB Output is correct
7 Correct 10 ms 2036 KB Output is correct
8 Correct 16 ms 2172 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 1860 KB Output is correct
11 Correct 16 ms 2108 KB Output is correct
12 Correct 17 ms 2128 KB Output is correct
13 Correct 17 ms 1864 KB Output is correct
14 Runtime error 1 ms 328 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -