QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #781148 | #7781. Sheep Eat Wolves | 4eyebird | RE | 1ms | 10604kb | C++17 | 2.8kb | 2024-11-25 14:56:21 | 2024-11-25 14:56:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Buff ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
//#define int long long
bool vis[110][110][110][110][2];
int p, q;
int bfs(ll x0, ll y0)
{
union I4s
{
unsigned short s[8];
unsigned int sx[2];
unsigned long long ssx;
} Ts;
Ts.s[0] = x0, Ts.s[1] = y0;
Ts.s[2] = 0, Ts.s[3] = 0;
Ts.sx[1] = 0;
queue<unsigned long long> qe;
qe.push(Ts.ssx);
vis[x0][y0][0][0][0] = 1;
while (!qe.empty())
{
Ts.ssx = qe.front();
qe.pop();
int x1 = Ts.s[0], y1 = Ts.s[1];
int x2 = Ts.s[2], y2 = Ts.s[3];
int as = Ts.sx[1];
int sp1 = p;
if (as & 1)
sp1 = min(x2, sp1);
else
sp1 = min(x1, sp1);
for (int i = sp1; i >= 0; i--)
{
int sp2 = p - i;
if (as & 1)
sp2 = min(y2, sp2);
else
sp2 = min(y1, sp2);
for (int j = sp2; j >= 0; j--)
{
if (as & 1)
{
if (x2 - i == 0 || x2 - i + q >= y2 - j)
{
if (!vis[x1 + i][y1 + j][x2 - i][y2 - j][!(as & 1)])
{
vis[x1 + i][y1 + j][x2 - i][y2 - j][!(as & 1)] = 1;
Ts.s[0] = x1 + i, Ts.s[1] = y1 + j;
Ts.s[2] = x2 - i, Ts.s[3] = y2 - j;
Ts.sx[1] = as + 1;
qe.push(Ts.ssx);
}
}
}
else
{
if (x1 - i == 0)
{
return as + 1;
}
if (x1 - i == 0 || x1 - i + q >= y1 - j)
{
if (!vis[x1 - i][y1 - j][x2 + i][y2 + j][!(as & 1)])
{
vis[x1 - i][y1 - j][x2 + i][y2 + j][!(as & 1)] = 1;
Ts.s[0] = x1 - i, Ts.s[1] = y1 - j;
Ts.s[2] = x2 + i, Ts.s[3] = y2 + j;
Ts.sx[1] = as + 1;
qe.push(Ts.ssx);
}
}
}
}
}
}
return -1;
}
void solve()
{
int x, y;
cin >> x >> y >> p >> q;
cout << bfs(x, y);
}
signed main()
{
#ifdef YGYYYGJ
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
Buff;
int _T_ = 1;
while (_T_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5636kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5612kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 6720kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 0ms
memory: 10604kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 0ms
memory: 6284kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: -100
Runtime Error
input:
60 60 8 1