QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #683869 | #7781. Sheep Eat Wolves | XiaoYang3 | ML | 43ms | 418388kb | C++23 | 2.7kb | 2024-10-28 00:54:03 | 2024-10-28 00:54:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, ll>;
ll n, m;
const int P = 1e9 + 7;
const int mod = 998244353;
void solve() {
int x, y, p, q;
cin >> x >> y >> p >> q;
queue<array<int, 5>> qq;
// memset(dis, 0x3f, sizeof dis);
int dis[x + 1][y + 1][x + 1][y + 1][2];
memset(dis, 0, sizeof dis);
int v[x + 1][y + 1][x + 1][y + 1][2];
memset(v, 0, sizeof v);
qq.push({x, y, 0, 0, 0});
dis[x][y][0][0][0] = 0;
v[x][y][0][0][0] = 1;
while (qq.size()) {
auto [x1, y1, x2, y2, fg] = qq.front();
qq.pop();
// cout << dis[2][4][1][1][0] << '\n';
if (fg % 2 == 0) {
// y1 <= x1 + q;
// 送样
for (int i = 0; i <= p; i++) {
int j = p - i;
if (i > x1 || j > y1) {
continue;
}
if (p >= x1) {
// cout << x1 << ' ' << y1 << '\n';
// dis[0][y1][x2 + x1][y2][fg ^ 1] =
// dis[x1][y1][x2][y2][fg] + 1;
// v[0][y1][x2 + x1][y1][fg ^ 1] = 1;
cout << dis[x1][y1][x2][y2][fg] + 1 << '\n';
return;
}
if (x1 - i + q < y1 - j) {
break;
}
if (!v[x1 - i][y1 - j][x2 + i][y2 + j][fg ^ 1]) {
v[x1 - i][y1 - j][x2 + i][y2 + j][fg ^ 1] = 1;
dis[x1 - i][y1 - j][x2 + i][y2 + j][fg ^ 1] =
dis[x1][y1][x2][y2][fg] + 1;
qq.push({x1 - i, y1 - j, x2 + i, y2 + j, fg ^ 1});
}
}
} else {
// 送狼
for (int i = 0; i <= p; i++) {
if (i > y2) {
break;
}
if (x2 + q < y2 - i && x2 != 0) {
continue;
}
if (!v[x1][y1 + i][x2][y2 - i][fg ^ 1]) {
v[x1][y1 + i][x2][y2 - i][fg ^ 1] = 1;
dis[x1][y1 + i][x2][y2 - i][fg ^ 1] =
dis[x1][y1][x2][y2][fg] + 1;
qq.push({x1, y1 + i, x2, y2 - i, fg ^ 1});
}
}
}
}
int ans = 1e9;
// cout << dis[2][4][1][1][0];
for (int i = 0; i <= y; i++) {
if (v[0][i][x][y - i][1]) {
// cout << ans << '\n';
ans = min(ans, dis[0][i][x][y - i][1]);
}
}
cout << (ans == 1e9 ? -1 : ans - 1) << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4004kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5572kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 0ms
memory: 13124kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 20ms
memory: 219884kb
input:
60 60 8 1
output:
27
result:
ok 1 number(s): "27"
Test #11:
score: 0
Accepted
time: 19ms
memory: 219892kb
input:
60 60 8 4
output:
27
result:
ok 1 number(s): "27"
Test #12:
score: 0
Accepted
time: 19ms
memory: 219924kb
input:
60 60 8 8
output:
25
result:
ok 1 number(s): "25"
Test #13:
score: 0
Accepted
time: 16ms
memory: 219928kb
input:
60 60 16 1
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 19ms
memory: 219900kb
input:
60 60 16 8
output:
11
result:
ok 1 number(s): "11"
Test #15:
score: 0
Accepted
time: 23ms
memory: 219968kb
input:
60 60 16 16
output:
11
result:
ok 1 number(s): "11"
Test #16:
score: 0
Accepted
time: 37ms
memory: 219848kb
input:
60 60 16 24
output:
9
result:
ok 1 number(s): "9"
Test #17:
score: 0
Accepted
time: 10ms
memory: 26588kb
input:
75 15 1 1
output:
175
result:
ok 1 number(s): "175"
Test #18:
score: 0
Accepted
time: 43ms
memory: 418388kb
input:
50 100 1 0
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: -100
Memory Limit Exceeded
input:
100 100 10 10