QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750670 | #7781. Sheep Eat Wolves | zhenghanyun# | WA | 0ms | 3660kb | C++14 | 1.6kb | 2024-11-15 15:24:57 | 2024-11-15 15:24:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
struct node {
int x, y, flg;
node() {}
node(int x, int y, int flg): x(x), y(y), flg(flg) {}
};
int x, y, p, q, ans = 1e9, f[N][N][2];
bitset <N> vis[N][2];
queue <node> Q;
inline void bfs(node s) {
Q.push(s);
vis[s.x][s.y][s.flg] = 1;
while (!Q.empty()) {
node u = Q.front();
Q.pop();
if (u.flg == 0) {
int s = x - u.x, t = y - u.y;
if (s && s + q < t) {
continue;
}
} else {
int s = u.x, t = u.y;
if (s && s + q < t) {
continue;
}
}
int d = f[u.x][u.y][u.flg];
if (u.x == 0) {
ans = d;
break;
}
if (u.flg == 0) {
for (int i = 0; i <= u.x; ++i) {
for (int j = 0; j <= u.y && i + j <= p; ++j) {
int nx = u.x - i, ny = u.y - j;
if (!vis[nx][ny][1]) {
Q.push(node(nx, ny, 1));
vis[nx][ny][1] = 1;
f[nx][ny][1] = d + 1;
}
}
}
} else {
for (int i = 0; i <= x - u.x; ++i) {
for (int j = 0; j <= y - u.y && i + j <= p; ++j) {
int nx = u.x + i, ny = u.y + j;
if (!vis[nx][ny][0]) {
Q.push(node(nx, ny, 0));
vis[nx][ny][0] = 1;
f[nx][ny][0] = d + 1;
}
}
}
}
}
}
int main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
assert(freopen("test.out", "w", stdout));
#endif
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> x >> y >> p >> q;
bfs(node(x, y, 0));
if (ans == 1e9) {
cout << "-1\n";
} else {
cout << ans << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3572kb
input:
18 40 16 7
output:
-1
result:
wrong answer 1st numbers differ - expected: '5', found: '-1'