oj.uz

Submission #1003428

# Submission time Handle Problem Language Result Execution time Memory
1003428 2024-06-20T10:12:38 Z thelepi Dijamant (COCI22_dijamant) C++17
70 / 70
 180 ms 8028 KB 
#include <iostream>
#include <algorithm>
#include <cassert>
#include <vector>

using namespace std;

bool inBounds(int x, int y, int n, int m){
  return x >= 0 && x < m && y >= 0 && y < n;
}
//End inclusive
bool isDiamond(vector<vector<char>> &table, int n, int m, int ax, int ay, int bx, int by){
  int sidelength = bx - ax + 1;
  //last row of #
  if(!inBounds(ax + sidelength - 1, ay + sidelength - 1, n, m) ||
     !inBounds(bx + sidelength - 1, by + sidelength - 1, n, m))
    return false;
  for (int i = 0; i < sidelength; i++)
  {
    if(table[ay + sidelength - 1 - i][ax + sidelength - 1 + i] != '#')
      return false;
  }

  for (int i = 1; i < sidelength - 1; i++)
  {
    //Side of #
    if(!inBounds(ax + i, ay + i, n, m) || 
       !inBounds(bx + i, by + i, n, m) ||
       table[ay + i][ax + i] != '#' ||
       table[by + i][bx + i] != '#')
      return false;
    //. between #
    for (int j = 1; j < sidelength - 1; j++)
    {
      if(table[ay + i - j][ax + i + j] != '.')
        return false;
    }
  }
  //rows without #
  for (int i = 0; i < sidelength - 1; i++)
  {
    for (int j = 0; j < sidelength - 1; j++)
    {
      if(table[ay + i - j][ax + i + j + 1] != '.')
        return false;
    }
  }
  return true;
}
//End inclusive
int countDiamonds(vector<vector<char>> &table, int n, int m, int ax, int ay, int bx, int by){
  int count = 0;
  while(bx - ax > 0){
    if(inBounds(ax + 1, ay + 1, n, m) && table[ay + 1][ax + 1] == '#'){
      int startx = ax;
      int starty = ay;
      do{
        ax++;
        ay--;
      } while(bx >= ax && inBounds(ax + 1, ay + 1, n, m) && table[ay + 1][ax + 1] == '.');
      if(bx < ax || !inBounds(ax + 1, ay + 1, n, m)){
        return count;
      }
      assert((table[ay + 1][ax + 1] == '#'));
      if(isDiamond(table, n, m, startx, starty, ax, ay))
        count++;
    }
    else{
      ax++;
      ay--;
    }
  }
  return count;
}

int main(int, char**){
  int n, m;
  cin >> n >> m;
  vector<vector<char>> table;
  table.resize(n);
  for (int i = 0; i < n; i++)
  {
    table[i].resize(m);
    for (int j = 0; j < m; j++)
    {
      cin >> table[i][j];
    }
  }
  int count = 0;
  for (int i = 1; i < n + m - 2; i++)
  {
    int start;
    bool inrange = false;
    int x;
    int y;
    for(int j = max(i + 1 - n, 0); j < min(i + 1, m); j++){
      x = j;
      y = i - j;
      if(table[y][x] == '.' && inrange){
        count += countDiamonds(table, n, m, start, i - start, x - 1, y + 1);
        inrange = false;
      }
      else if(table[y][x] == '#' && !inrange){
        start = j;
        inrange = true;
      }
    }
    if(inrange){
      count += countDiamonds(table, n, m, start, i - start, x, y);
    }
  }
  cout << count << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 440 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 440 KB Output is correct
14 Correct 129 ms 7416 KB Output is correct
15 Correct 169 ms 7656 KB Output is correct
16 Correct 180 ms 7140 KB Output is correct
17 Correct 111 ms 7132 KB Output is correct
18 Correct 159 ms 8016 KB Output is correct
19 Correct 94 ms 6896 KB Output is correct
20 Correct 109 ms 8028 KB Output is correct
21 Correct 93 ms 6868 KB Output is correct
22 Correct 127 ms 7372 KB Output is correct
23 Correct 100 ms 6996 KB Output is correct
24 Correct 136 ms 7504 KB Output is correct
25 Correct 115 ms 6736 KB Output is correct
26 Correct 118 ms 7248 KB Output is correct