QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87091 | #3002. Busy Board | KHIN | WA | 63ms | 5384kb | C++17 | 2.6kb | 2023-03-11 17:01:12 | 2023-03-11 17:03:15 |
Judging History
answer
# include <cstdlib>
# include <functional>
# include <cassert>
# include <vector>
# include <algorithm>
# include <numeric>
# include <iostream>
# include <ostream>
namespace khin {
using namespace std;
namespace main {
inline namespace source {}
namespace b { void main(); }
}
}
int main() { khin::main::b::main(); }
namespace khin::main::b {
constexpr uint r_max(1'000), c_max(1'000);
class disjoint_set_union {
uint mo[r_max + c_max + 1];
uint sz[r_max + c_max + 1];
public:
constexpr disjoint_set_union() : mo{}, sz{} {
iota(mo, mo + r_max + c_max + 1, 0u);
fill(sz, sz + r_max + c_max + 1, 1u);
}
constexpr uint find(uint const x)
{ return mo[x] == x ? x : mo[x] = find(mo[x]); }
constexpr void merge(uint x, uint y) {
if ((x = find(x)) == (y = find(y))) return;
if (sz[x] < sz[y]) swap(x, y);
mo[y] = x, sz[x] += sz[y], sz[y] = 0;
}
};
uint r, c; char s[r_max][c_max], t[r_max][c_max]; disjoint_set_union dsu;
inline bool chkr(uint const x) { return dsu.find(x + 1) == dsu.find(0); }
inline bool chkc(uint const x) { return dsu.find(x + r + 1) == dsu.find(0); }
void main() {
cin >> r >> c;
for (uint i(0); i < r; ++i) for (uint j(0); j < c; ++j) cin >> s[i][j];
for (uint i(0); i < r; ++i) for (uint j(0); j < c; ++j) cin >> t[i][j];
bool const equal = [] {
for (uint i(0); i < r; ++i) for (uint j(0); j < c; ++j)
if (s[i][j] != t[i][j]) return false;
return true;
} ();
if (equal) return cout << 1 << endl, void();
for (uint i(0); i < r; ++i) for (uint j(0); j < c; ++j)
if (t[i][j] == 'X') dsu.merge(i + 1, j + r + 1);
for (uint i(0); i < r; ++i)
if (count(t[i], t[i] + c, 'X') > 1) dsu.merge(i + 1, 0);
for (uint i(0); i < c; ++i) {
uint cnt(0);
for (uint j(0); j < r; ++j) cnt += t[j][i] == 'X';
if (cnt > 1) dsu.merge(i + r + 1, 0);
}
bool cso(false), csx(false), cto(false), ctx(false);
for (uint i(0); i < r; ++i) for (uint j(0); j < c; ++j) {
if (chkr(i) && chkc(j) && t[i][j] == 'X')
return cout << 0 << endl, void();
if (!chkr(i) && !chkc(j)) {
cso = cso || s[i][j] == 'O', csx = csx || s[i][j] == 'X';
cto = cto || t[i][j] == 'O', ctx = ctx || t[i][j] == 'X';
}
}
if ((!cso && cto) || (!ctx && csx))
return cout << 0 << endl, void();
if (!cso || !ctx) {
for (uint i(0); i < r; ++i) for (uint j(0); j < c; ++j)
if ((chkr(i) || chkc(j)) && s[i][j] != t[i][j])
return cout << 0 << endl, void();
return cout << 1 << endl, void();
}
cout << 1 << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 54ms
memory: 4772kb
input:
769 998 OOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOO...
output:
0
result:
ok answer is 0
Test #2:
score: 0
Accepted
time: 51ms
memory: 5264kb
input:
977 998 OOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOO...
output:
0
result:
ok answer is 0
Test #3:
score: -100
Wrong Answer
time: 63ms
memory: 5384kb
input:
941 973 XOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXOXXXXXXXOXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
0
result:
wrong answer expected 1, found 0