oj.uz

Submission #630853

# Submission time Handle Problem Language Result Execution time Memory
630853 2022-08-17T08:56:11 Z Chal1shkan Dijamant (COCI22_dijamant) C++14
70 / 70
 371 ms 240952 KB 
# include <bits/stdc++.h>

# define mkp make_pair
# define ff first
# define ss second
# define pll pair <ll, ll>
# define pii pair <int, int>
 
# define vec vector
# define pb push_back
# define pf push_front
# define ppb pop_back
# define ppf pop_front

# define all(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
# define sz(x) ((int)(x).size())
# define lb lower_bound
# define ub upper_bound

# define br break
# define rt return 
# define cn continue
# define nl "\n"
# define off exit(0)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll MAXN = 3e5 + 25;
const ll MAXL = 18 + 0;
const ll INF1 = 1e18 + 0;
const ll INF2 = 2e9 + 0;
const ll MOD = 1e9 + 7;
const ll M0D = 998244353;
const ld PI = acos((ld) -1);
const ll P = 67 + 0 + 0;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

using namespace std;

ll n, m, cnt, ok;
char x[2025][2025];
bool used[2025][2025];
ll a, b, c, d;

void dfs (ll i, ll j)
{
	if (used[i][j] || x[i][j] == '#') rt;
	if (i < 1 || i > n || j < 1 || j > m)
	{
		ok = 0;
		rt;
	}
	used[i][j] = 1; cnt++;
    a = max(a, i + j); b = min(b, i + j);
    c = max(c, i - j); d = min(d, i - j);
	for (ll id = 0; id < 4; ++id)
	{
		dfs(i + dx[id], j + dy[id]);
	}
}

void ma1n ()
{
	cin >> n >> m;
	for (ll i = 1; i <= n; ++i)
	{
		for (ll j = 1; j <= m; ++j)
		{
			cin >> x[i][j];
		}
	}
	ll ans = 0;
	for (ll i = 1; i <= n; ++i)
	{
		for (ll j = 1; j <= m; ++j)
		{
			if (x[i][j] == '#' || used[i][j]) cn;
			a = -1e9, b = 1e9;
			c = -1e9, d = 1e9;
			ok = 1, cnt = 0;
			dfs(i, j);
			if (a - b == c - d)
			{
				if ((a - b) % 2 == 0)
				{
					if (ok)
					{
						ll nd = ((a - b) / 2 + 1);
						if (cnt == 2 * nd * nd - 2 * nd + 1)
						{
							ans++;
						}
					}
				}
			}
		}
	}
	cout << ans << nl;
}
	
int main (/*?*/)
{	
	int zxc = 1;
//	cin >> zxc;
	while (zxc--)
	{
		ma1n();
	}
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 1084 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Correct 1 ms 596 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 1084 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 371 ms 240952 KB Output is correct
15 Correct 208 ms 7700 KB Output is correct
16 Correct 259 ms 11084 KB Output is correct
17 Correct 335 ms 166396 KB Output is correct
18 Correct 242 ms 12028 KB Output is correct
19 Correct 254 ms 53188 KB Output is correct
20 Correct 286 ms 46596 KB Output is correct
21 Correct 244 ms 29004 KB Output is correct
22 Correct 267 ms 19020 KB Output is correct
23 Correct 245 ms 17712 KB Output is correct
24 Correct 261 ms 19008 KB Output is correct
25 Correct 337 ms 211380 KB Output is correct
26 Correct 209 ms 10828 KB Output is correct