oj.uz

Submission #825958

# Submission time Handle Problem Language Result Execution time Memory
825958 2023-08-15T09:34:17 Z vjudge1 Dijamant (COCI22_dijamant) C++14
70 / 70
 211 ms 234616 KB 
#include <bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=2e3+11;
bool a[N][N];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n, m;
bool inbound(int x,int y)
{
    return (x>=0 && y>=0);
}
int ma1, ma2, mi1, mi2;
int cnt = 0;
void dfs(int x,int y)
{
    a[x][y]=1;
    cnt++;
    ma1 = max(ma1,x+y);
    mi1 = min(mi1,x+y);
    ma2 = max(ma2,x-y);
    mi2 = min(mi2,x-y);
    for(int i=0; i<4; i++)
        if(inbound(x+dx[i], y+dy[i]))
            if(a[x+dx[i]][y+dy[i]]==0)
                dfs(x+dx[i],y+dy[i]);
}
void sol()
{
    cin >> m >> n;
    for(int i=0; i<2005; i++)
    {
        a[i][n+4]=1;
        a[m+4][i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            char x;
            cin >> x;
            if(x=='#') a[i][j]=1;
                
        }
    }
    int ans = 0;
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(!a[i][j])
            {
                ma1=ma2=INT_MIN;
                mi1=mi2=INT_MAX;
                cnt=0;
                dfs(i,j);
                if(ma1-mi1!=ma2-mi2 || (ma1-mi1)%2) continue;
                int l = (ma1-mi1)/2+1;
                int ss = (2*l*l)-(2*l)+1;
                if(cnt == ss) ans++;
            }
        }
    }
    cout << ans;
}
signed main()
{
//    freopen("task.INP", "r", stdin);
//    freopen("task.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 2 ms 4692 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4820 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4564 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4308 KB Output is correct
7 Correct 2 ms 4308 KB Output is correct
8 Correct 2 ms 4308 KB Output is correct
9 Correct 2 ms 4308 KB Output is correct
10 Correct 2 ms 4308 KB Output is correct
11 Correct 2 ms 4308 KB Output is correct
12 Correct 2 ms 4692 KB Output is correct
13 Correct 2 ms 4180 KB Output is correct
14 Correct 211 ms 234616 KB Output is correct
15 Correct 36 ms 4180 KB Output is correct
16 Correct 102 ms 5016 KB Output is correct
17 Correct 131 ms 115184 KB Output is correct
18 Correct 55 ms 4940 KB Output is correct
19 Correct 85 ms 31772 KB Output is correct
20 Correct 104 ms 47908 KB Output is correct
21 Correct 85 ms 38664 KB Output is correct
22 Correct 89 ms 13100 KB Output is correct
23 Correct 89 ms 20644 KB Output is correct
24 Correct 91 ms 18460 KB Output is correct
25 Correct 176 ms 169448 KB Output is correct
26 Correct 56 ms 4960 KB Output is correct