Submission #540371

#	Time	Username	Problem	Language	Result	Execution time	Memory
540371		N1NT3NDO	Dijamant (COCI22_dijamant)	C++14	0 / 70	2 ms	1364 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 2100;
int n, m, up_down[N][N], left_right[N][N];
char c[N][N];
int d1[2 * N][N], d2[2 * N][N], ans;

bool good1(int x, int y, int x1, int y1)
{
    while(x != x1 || y != y1)
    {
        if (c[x][y] != '#') return 0;
        x++; y++;
    }

    return 1;
}

bool good2(int x, int y, int x1, int y1)
{
    while(x != x1 || y != y1)
    {
        if (c[x][y] != '#') return 0;
        x--; y++;
    }

    return 1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        cin >> c[i][j];

    for(int i = 1; i <= n; i++)
    {
        int lst = -1e9;
        for(int j = 1; j <= m; j++)
        {
            if (c[i][j] == '#') lst = j;
            left_right[i][j] = j - lst;
        }

        lst = 1e9;

        for(int j = m; j >= 1; j--)
        {
            if (c[i][j] == '#') lst = j;
            left_right[i][j] = min(left_right[i][j], lst - j);
        }
    }

    for(int j = 1; j <= m; j++)
    {
        int lst = -1e9;
        for(int i = 1; i <= n; i++)
        {
            if (c[i][j] == '#') lst = i;
            up_down[i][j] = i - lst;
        }

        lst = 1e9;

        for(int i = n; i >= 1; i--)
        {
            if (c[i][j] == '#') lst = i;
            up_down[i][j] = min(up_down[i][j], lst - i);
        }
    }

    /*
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        {
            if (up_down[i][j] > n + m) up_down[i][j] = 1e9;
            if (left_right[i][j] > n + m) left_right[i][j] = 1e9;
        }
    */

    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
      {
          int d = min(up_down[i][j], left_right[i][j]);
          if (d == 0) continue;
          if (i - d <= 0 || i + d > n || j + d > m || j - d <= 0) continue;
          if (c[i - d][j] != '#' || c[i + d][j] != '#' || c[i][j - d] != '#' || c[i][j + d] != '#') continue;
          if (good1(i - d, j, i, j + d) && good1(i, j - d, i + d, j) && good2(i + d, j, i, j + d) && good2(i, j - d, i - d, j)) ans++;
      }

    cout << ans;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 50