Submission #1003428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003428		thelepi	Dijamant (COCI22_dijamant)	C++17	70 / 70	180 ms	8028 KiB

Main

#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 / 20
• Subtask 2: 50 / 50