oj.uz

Submission #540373

# Submission time Handle Problem Language Result Execution time Memory
540373 2022-03-20T07:48:34 Z N1NT3NDO Dijamant (COCI22_dijamant) C++14
0 / 70
 2 ms 1876 KB 
#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, diag1[N][N], diag2[N][N];

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;
}

bool good(int x1, int y1, int x2, int y2)
{
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        if (i > x1 && i < x2 && j > y1 && j < y2 && c[i][j] == '#')
        {
            cout << i << ' ' << j << ' ' << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
            return 0;
        }

    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 j = 1; j <= m; j++)
    {
        int lst = -1e9;
        int x = j, y = 1;
        for(int skok = 1; x >= 1 && y <= m; x--, y++, skok++)
        {
            if (c[x][y] == '#') lst = skok;
            diag1[x][y] = skok - lst;
        }

        lst = -1e9;
        x++; y--;
        for(int skok = 1; x <= n && y >= 1; x++, y--, skok++)
        {
            if (c[x][y] == '#') lst = skok;
            diag1[x][y] = min(diag1[x][y], skok - lst);
        }
    }

    for(int j = 1; j <= m; j++)
    {
        int lst = -1e9;
        int x = n, y = j;
        for(int skok = 1; x >= 1 && y <= m; x--, y++, skok++)
        {
            if (c[x][y] == '#') lst = skok;
            diag1[x][y] = skok - lst;
        }

        lst = -1e9;
        x++; y--;
        for(int skok = 1; x <= n && y >= 1; x++, y--, skok++)
        {
            if (c[x][y] == '#') lst = skok;
            diag1[x][y] = min(diag1[x][y], skok - lst);
        }
    }


//    for(int i = 1; i <= n; i++)
//      for(int j = 1; j <= m; j++)
//        {
//            cout << i << ' ' << j << ' ' << diag1[i][j] << endl;
//        }



    /*
    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 = 0;
          int d = min({up_down[i][j], left_right[i][j], diag1[i][j] + 1});
          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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Incorrect 1 ms 1748 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1748 KB Output is correct
2 Correct 1 ms 1748 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Incorrect 1 ms 1748 KB Output isn't correct
7 Halted 0 ms 0 KB -