Submission #759064

#	Time	Username	Problem	Language	Result	Execution time	Memory
759064		harut_13	Dijamant (COCI22_dijamant)	C++14	70 / 70	114 ms	22088 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <ios>
#include <iomanip>
#include <deque>
#include <queue>
#include <list> 
#include <stack>

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(NULL);
#define CY   cout<<"YES"<<endl
#define CN   cout<<"NO"<<endl
#define ll   long long
#define ciN  cin
#define itn  int
#define pshb  push_back
#define sz  size()
#define vec vector<int>
#define vecl vector<long long>
#define fro for
#define Int int
#define stirng string
#define nedl   endl 
#define pi 3.141592653589793238463
#define endl '\n'
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>


using namespace std;

ll gcd(ll n1, ll n2)
{
    if (n2 != 0)
        return gcd(n2, n1 % n2);
    else
        return n1;
}
ll lcm(ll a, ll b) {
    return a * b / (gcd(a, b));
}

ll pv(ll a, ll b) {
    if (b == 0)return 1;
    ll res = pv(a, b / 2);
    if (b % 2) {
        return (res * res) * a;
    }
    else {
        return (res * res);
    }
}

vector < vector<char>> v;
bool vand(int i, int j) {
    if (v[i][j] == '#')return 1;
    else return 0;
}

void solve() {
    int n, m; cin >> n >> m;
    v = vector < vector<char>>(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
    }
    vector<vec> right(n, vec(m, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j)) {
                for (int k = j + 1; k < m; k++) {
                    if (vand(i, k)) {
                        right[i][j] = k; break;
                    }
                }
                if (right[i][j] != -1)j = right[i][j]-1;
                else break;
            }
        }
    }

    vector<vector<bool>> a(n, vector<bool>(m)), b(n, vector<bool>(m)), c(n, vector<bool>(m)), d(n, vector<bool>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j)) {
                if (right[i][j] != -1  ) {
                    if ((right[i][j] - j) == 2 && i != 0) {
                        if (vand(i - 1, j + 1)) {
                            a[i][j] = 1;
                            b[i][right[i][j]] = 1;
                        }
                    }
                    else {
                        if (i != 0) {
                            if (a[i - 1][j + 1] && b[i - 1][right[i][j] - 1] && right[i-1][j+1]==right[i][j]-1) {
                                a[i][j] = 1;
                                b[i][right[i][j]] = 1;
                            } 
                        }
                    }
                }
            }
        }
    }
    for (int i = n - 1; i >= 0;i--) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j)) {
                if (right[i][j] != -1 && ((right[i][j] - j) % 2 == 0)) {
                    if ((right[i][j] - j) == 2 && i != n-1) {
                        if (vand(i + 1, j + 1)) {
                            c[i][j] = 1;
                            d[i][right[i][j]] = 1;
                        }
                    }
                    else {
                        if (i != n - 1) {
                            if (c[i + 1][j + 1] && d[i + 1][right[i][j] - 1] && right[i+1][j+1]==right[i][j]-1) {
                                c[i][j] = 1;
                                d[i][right[i][j]] = 1;
                            }
                        }
                    }
                }
            }
        }
    }
    
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vand(i, j) && right[i][j] != -1) {
                if (a[i][j] && c[i][j] && b[i][right[i][j]] && d[i][right[i][j]]) {
                    cnt++;
                   // cout << i << " " << j << i << " " << right[i][j] << endl;
                }
            }
           // cout << a[i][j];
        }
        //cout << endl;
    }
    cout << cnt << endl;
}
int main() {
    FASTIO

        //int t; cin >> t;
    //while (t--)
        solve();
}

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