Submission #759072

#	Time	Username	Problem	Language	Result	Execution time	Memory
759072		boris_7	Dijamant (COCI22_dijamant)	C++17	70 / 70	100 ms	38476 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
int n,m;

bool check(int i,int j){
    return (i>=0 && j>=0 && i<n && j<m);
}

void solve(){
    cin>>n>>m;
    vector<string>v(n);
    for(int i = 0;i<n;i++){
        cin>>v[i];
    }
    vector<vector<int>>pref(n,vector<int>(m));
    vector<vector<int>>e(n);
    for(int i = 0;i<n;i++){
        if(v[i][0]=='#'){
            pref[i][0]=1;
            e[i].push_back(0);
        }
    }
    for(int i =0;i<n;i++){
        for(int j = 1;j<m;j++){
            pref[i][j]=pref[i][j-1]+(v[i][j]=='#');
            if(v[i][j]=='#') e[i].push_back(j);
        }
    }
    vector<vector<bool>>a,b,c,d;
    a = b = c = d = vector<vector<bool>>(n,vector<bool>(m));
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(check(i+1,j-1) && check(i+1,j+1) && v[i][j]=='#' && v[i+1][j-1] == '#' && v[i+1][j+1] == '#' && v[i+1][j]=='.'){
                a[i + 1][j - 1] = 1;
                b[i + 1][j + 1] = 1;
            }
            if(check(i-1,j-1) && check(i-1,j+1) && v[i][j]=='#' && v[i-1][j-1] == '#' && v[i-1][j+1] == '#' && v[i-1][j]=='.'){
                c[i-1][j-1]=1;
                d[i-1][j+1]=1;
            }
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j+1<e[i].size();j++){
            int x1 = e[i][j];
            int x2 = e[i][j+1];
            if(check(i-1,x1+1) && check(i-1,x2-1) && pref[i-1][x2-1]-pref[i-1][x1+1]==1){
                if(check(i-1,x1+1) && check(i-1,x2-1) && a[i-1][x1+1] && b[i-1][x2-1]){
                    a[i][x1]=1;
                    b[i][x2]=1;
                }
            }
        }
    }
    for(int i = n-1;i>=0;i--){
        for(int j = 0;j+1<e[i].size();j++){
            int x1 = e[i][j];
            int x2 = e[i][j+1];
            if(check(i+1,x1+1) && check(i+1,x2-1) && pref[i+1][x2-1]-pref[i+1][x1+1]==1){
                if(check(i+1,x1+1) && check(i+1,x2-1) && c[i+1][x1+1] && d[i+1][x2-1]){
                    c[i][x1]=1;
                    d[i][x2]=1;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1;i+1<n;i++){
        for(int j = 0;j+1<e[i].size();j++){
            int x1 = e[i][j];
            int x2 = e[i][j+1];
            if(a[i][x1] && c[i][x1] && b[i][x2] && d[i][x2]){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 0;j+1<e[i].size();j++){
      |                       ~~~^~~~~~~~~~~~
Main.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(int j = 0;j+1<e[i].size();j++){
      |                       ~~~^~~~~~~~~~~~
Main.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0;j+1<e[i].size();j++){
      |                       ~~~^~~~~~~~~~~~

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