QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#318775 | #7733. Cool, It’s Yesterday Four Times More | amirali_asgari# | WA | 2ms | 5736kb | C++20 | 2.6kb | 2024-01-31 20:14:01 | 2024-01-31 20:14:01 |
Judging History
answer
// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define X real()
#define Y imag()
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
int n, m;
const int maxn = 2e5 + 4;
vector<char> s[maxn]; int M[maxn];
int mark[maxn], col[maxn], c = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<pii> A[maxn];
int GI(int i, int j) {
return (i * m + j);
}
pii Gp(int v) {
return Mp(v / m, v % m);
}
void dfs(int v) {
auto f = Gp(v);
int x = f.F, y = f.S;
mark[v] = 1; col[v] = c; A[c].pb(Mp(x, y));
for (int T = 0; T < 4; T++) {
int x1 = x + dx[T], y1 = y + dy[T];
if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && s[x1][y1] == '.') {
int u = GI(x1, y1);
if (!mark[u]) dfs(u);
}
}
}
bool ok(int i, int j) {
auto f = A[i][0];
for (auto g : A[j]) {
pii d = Mp(g.F - f.F, g.S - f.S);
bool flag = 1;
for (auto r : A[i]) {
int x1 = r.F + d.F, y1 = r.S + d.S;
if (!(x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && col[GI(x1, y1)] == j)) {
flag = 0;
break;
}
}
if (flag) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
for (int i = 0; i < n; i++) {
s[i].clear(); s[i].resize(m);
for (int j = 0; j < m; j++) cin >> s[i][j];
}
fill(mark, mark + (n * m), 0); c = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] != '.') continue;
int v = GI(i, j);
if (!mark[v]) {
A[c].clear();
dfs(v); c++;
}
}
}
fill(M, M + c, 1);
for (int i = 0; i < c; i++) {
for (int j = i + 1; j < c; j++) {
if (len(A[i]) == len(A[j])) {
if (ok(i, j)) {
M[i] = 0; M[j] = 0;
}
}
else if (len(A[i]) > len(A[j])) {
if (ok(j, i)) M[j] = 0;
}
else {
if (ok(i, j)) M[i] = 0;
}
}
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] != '.') continue;
int v = GI(i, j);
if (M[col[v]]) res++;
}
}
cout << res << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5736kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
3 1 0 0
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 5688kb
input:
200 2 4 OOO. OO.. 2 3 OOO .O. 3 3 O.O OOO OO. 4 1 . . O O 1 2 .O 1 1 . 2 5 .OO.. .O.O. 2 1 O O 1 1 O 1 3 .OO 5 1 O O . O . 5 2 O. .. O. .O .. 5 3 ... ... .OO ..O OOO 3 5 ..O.O .O.O. .OO.O 5 2 .O OO O. O. .. 2 1 O O 3 5 .O.OO O...O ..OO. 1 5 ..... 5 1 O . O . . 5 3 OOO OO. .OO OO. O.O 2 1 O . 5 2 O. ...
output:
3 0 0 2 1 1 3 0 0 1 0 7 9 4 4 0 6 5 2 0 1 6 4 5 2 0 0 5 3 3 1 4 1 0 4 5 2 3 7 3 0 6 2 2 2 0 4 6 6 3 3 2 3 3 2 1 0 3 3 4 4 2 2 0 7 6 4 8 5 3 2 5 2 1 2 1 4 0 0 2 5 1 4 6 6 1 6 2 2 3 4 5 2 1 0 1 9 3 4 11 0 3 2 1 0 0 4 3 1 4 3 8 3 0 3 6 2 5 1 3 3 4 0 2 11 2 2 4 0 4 0 6 2 1 2 3 0 5 0 16 4 3 2 6 0 8 3 3 1...
result:
wrong answer 35th lines differ - expected: '7', found: '4'