QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376807 | #3161. Another Coin Weighing Puzzle | ckiseki# | WA | 1ms | 3820kb | C++20 | 5.1kb | 2024-04-04 16:53:21 | 2024-04-04 16:53:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << "\n";
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
cerr << "\e[1;32m(" << s << ") = (";
int f = 0;
(..., (cerr << (f++ ? ", " : "") << a));
cerr << ")\e[0m\n";
}
#include <experimental/iterator>
void orange_(auto s, auto L, auto R) {
cerr << "\e[1;33m[ " << s << " ] = [ ";
using namespace experimental;
copy(L, R, make_ostream_joiner(cerr, ", "));
cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif
class DSU {
vector<int> a;
public:
DSU(int n) : a(n) {
iota(all(a), 0);
}
int query(int x) {
if (a[x] != x)
a[x] = query(a[x]);
return a[x];
}
void join(int x, int y) {
debug("join", x, y);
a[query(x)] = query(y);
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (auto &ai : a)
cin >> ai;
constexpr int INF = 1 << 30;
DSU dsu(n * m * 2 + 1);
auto go = [&](int x, int y, int dx, int dy, int o) {
debug("go", x, y, dx, dy);
while (true) {
x += dx, y += dy;
if (x < 0 or x >= n) {
x -= dx;
dx = -dx;
}
if (y < 0 or y >= m) {
y -= dy;
dy = -dy;
}
debug("now", x, y);
const int t = (x * m + y) * 2;
if (a[x][y] == '/') {
swap(dx, dy);
} else if (a[x][y] == '\\') {
swap(dx, dy);
dx = -dx, dy = -dy;
} else if (a[x][y] == '#') {
dsu.join(o, n * m * 2);
break;
} else if (a[x][y] == 'V') {
dsu.join(o, t + (dx == 0));
break;
} else if (a[x][y] == 'H') {
dsu.join(o, t + (dy == 0));
break;
}
}
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
const int o = (i * m + j) * 2;
if (a[i][j] == 'V') {
go(i, j, -1, 0, o);
go(i, j, 1, 0, o);
go(i, j, 0, -1, o + 1);
go(i, j, 0, 1, o + 1);
} else if (a[i][j] == 'H') {
go(i, j, -1, 0, o + 1);
go(i, j, 1, 0, o + 1);
go(i, j, 0, -1, o);
go(i, j, 0, 1, o);
}
}
}
vector<int> cost(n * m * 2 + 1);
debug(dsu.query(n * m * 2));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 'V' or a[i][j] == 'H') {
const int o = (i * m + j) * 2;
debug(i, j, dsu.query(o), dsu.query(o + 1));
if (dsu.query(o) == dsu.query(o + 1)) {
cout << "-1\n";
return 0;
}
cost[dsu.query(o + 1)]++;
if (dsu.query(o) == dsu.query(n * m * 2))
cost[dsu.query(o)] = INF;
if (dsu.query(o + 1) == dsu.query(n * m * 2))
cost[dsu.query(o + 1)] = INF;
}
}
}
int64_t ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 'V' or a[i][j] == 'H') {
const int o = (i * m + j) * 2;
if (dsu.query(o) == o) {
ans += min(cost[dsu.query(o)], cost[dsu.query(o + 1)]);
}
}
}
}
if (ans >= INF)
ans = -1;
cout << ans << '\n';
return 0;
}
/*
2 5
V...\
H...V
("go", x, y, dx, dy) = (go, 0, 0, -1, 0)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 0, 0)
("go", x, y, dx, dy) = (go, 0, 0, 1, 0)
("now", x, y) = (now, 1, 0)
("join", x, y) = (join, 0, 11)
("go", x, y, dx, dy) = (go, 0, 0, 0, -1)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 1, 1)
("go", x, y, dx, dy) = (go, 0, 0, 0, 1)
("now", x, y) = (now, 0, 1)
("now", x, y) = (now, 0, 2)
("now", x, y) = (now, 0, 3)
("now", x, y) = (now, 0, 4)
("now", x, y) = (now, 0, 4)
("now", x, y) = (now, 0, 3)
("now", x, y) = (now, 0, 2)
("now", x, y) = (now, 0, 1)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 1, 1)
("go", x, y, dx, dy) = (go, 1, 0, -1, 0)
("now", x, y) = (now, 0, 0)
("join", x, y) = (join, 11, 0)
("go", x, y, dx, dy) = (go, 1, 0, 1, 0)
("now", x, y) = (now, 1, 0)
("join", x, y) = (join, 11, 11)
("go", x, y, dx, dy) = (go, 1, 0, 0, -1)
("now", x, y) = (now, 1, 0)
("join", x, y) = (join, 10, 10)
("go", x, y, dx, dy) = (go, 1, 0, 0, 1)
("now", x, y) = (now, 1, 1)
("now", x, y) = (now, 1, 2)
("now", x, y) = (now, 1, 3)
("now", x, y) = (now, 1, 4)
("join", x, y) = (join, 10, 19)
("go", x, y, dx, dy) = (go, 1, 4, -1, 0)
("now", x, y) = (now, 0, 4)
("now", x, y) = (now, 0, 4)
("now", x, y) = (now, 1, 4)
("join", x, y) = (join, 18, 18)
("go", x, y, dx, dy) = (go, 1, 4, 1, 0)
("now", x, y) = (now, 1, 4)
("join", x, y) = (join, 18, 18)
("go", x, y, dx, dy) = (go, 1, 4, 0, -1)
("now", x, y) = (now, 1, 3)
("now", x, y) = (now, 1, 2)
("now", x, y) = (now, 1, 1)
("now", x, y) = (now, 1, 0)
("join", x, y) = (join, 19, 10)
("go", x, y, dx, dy) = (go, 1, 4, 0, 1)
("now", x, y) = (now, 1, 4)
("join", x, y) = (join, 19, 19)
(dsu.query(n * m * 2)) = (20)
(i, j, dsu.query(o), dsu.query(o + 1)) = (0, 0, 11, 1)
(i, j, dsu.query(o), dsu.query(o + 1)) = (1, 0, 19, 11)
(i, j, dsu.query(o), dsu.query(o + 1)) = (1, 4, 18, 19)
0
*/
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3820kb
input:
2 1
output:
0
result:
wrong answer 1st lines differ - expected: '9', found: '0'