oj.uz

Submission #759063

# Submission time Handle Problem Language Result Execution time Memory
759063 2023-06-15T17:52:45 Z harut_13 Dijamant (COCI22_dijamant) C++14
70 / 70
 132 ms 23328 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 47 ms 21824 KB Output is correct
15 Correct 79 ms 22360 KB Output is correct
16 Correct 132 ms 20920 KB Output is correct
17 Correct 65 ms 20684 KB Output is correct
18 Correct 88 ms 23328 KB Output is correct
19 Correct 49 ms 20020 KB Output is correct
20 Correct 62 ms 23284 KB Output is correct
21 Correct 47 ms 20044 KB Output is correct
22 Correct 78 ms 21324 KB Output is correct
23 Correct 65 ms 20280 KB Output is correct
24 Correct 79 ms 21780 KB Output is correct
25 Correct 45 ms 20004 KB Output is correct
26 Correct 57 ms 20616 KB Output is correct