# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1003388 | Nailuj_217 | Dijamant (COCI22_dijamant) | C++17 | 159 ms | 36352 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define l long long
using namespace std;
const l INF = 1LL<<15;
array<vector<l>, 2005> rows;
array<l, 2005> positions;
//i is current y
//k is the x
void update(l k, l j) {
if (positions[k] == INF) return;
if (rows[k].empty()) {
positions[k] = INF;
return;
}
while (rows[k][positions[k]] < j) {
if (rows[k].size() > positions[k]+1) positions[k]++;
else {
positions[k] = INF;
return;
}
}
}
int main() {
l n, m;
cin >> n >> m;
string row;
if (n == 1 || m == 1) {
cout << 0 << endl;
return 0;
}
l sum = 0;
for (int i = 1; i <= n; i++) {
cin >> row;
for (int j = 0; j < row.size(); j++) {
if (row[j] == '#') rows[i].push_back(j+1);
}
}
l dist_to_left;
for (int i = 2; i < n; i++) {
positions.fill(0);
for (int j = 1; j < m; j++) {
// for (int k = 1; k <= n; k ++)
// update(k, j);
update(i, j);
if (!positions[i]) continue;
if (positions[i] == INF) continue;
dist_to_left = j - rows[i][positions[i]-1];
assert(dist_to_left >= 0);
if (i - dist_to_left < 1 || i + dist_to_left > n || j + dist_to_left > m) continue;
if (j + dist_to_left != rows[i][positions[i]]) continue;
bool is_valid = true;
if (!is_valid) continue;
l c = 0;
for (int k = i - dist_to_left; k < i; k++) {
update(k, j);
assert(k > 0);
if (positions[k] == INF) {
is_valid = false;
break;
}
if (c == 0) {
if (rows[k][positions[k]] != j) {
is_valid = false;
break;
}
} else {
if (positions[k] == 0 || rows[k][positions[k]-1] != j-c) {
is_valid = false;
break;
}
if (positions[k] == 0 || rows[k][positions[k]] != j+c) {
is_valid = false;
break;
}
}
c++;
}
c = 0;
for (int k = i + dist_to_left; k > i; k--) {
update(k, j);
assert(k <= n);
if (positions[k] == INF) {
is_valid = false;
break;
}
if (c == 0) {
if (rows[k][positions[k]] != j) {
is_valid = false;
break;
}
} else {
if (positions[k] == 0 || rows[k][positions[k]-1] != j-c) {
is_valid = false;
break;
}
if (positions[k] == 0 || rows[k][positions[k]] != j+c) {
is_valid = false;
break;
}
}
c++;
}
if (is_valid) {
sum++;
continue;}
}
}
cout << sum << endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |