QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #362424 | #7781. Sheep Eat Wolves | Sunlight9# | AC ✓ | 169ms | 4532kb | C++14 | 1.5kb | 2024-03-23 15:28:52 | 2024-10-14 07:48:59 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define rep(i,t,n) for (int i=t;i<=n;i++)
#define endl '\n'
using namespace std;
int x,y,p,q;
int f[2][205][205];
struct node{
int s,w,flag;//0 l to r
};
queue<node> b;
void bfs(){
b.push((node){x,y,0});
while (!b.empty()){
node t=b.front();b.pop();
//cout<<t.s<<' '<<t.w<<' '<<t.flag<<' '<<f[t.flag][t.s][t.w]<<endl;
for (int i=0;i<=x;i++) {
for (int j=0;j<=y;j++){
if (i+j>p) continue;
if (t.flag==0) {
int ls=t.s,lw=t.w,rs=x-t.s,rw=y-t.w;
if (ls-i<0||rs+i>x||lw-j<0||rw+j>y) continue;
if (ls-i+q<lw-j&&ls-i!=0) continue;
if (f[1][rs+i][rw+j]>f[0][ls][lw]+1) f[1][rs+i][rw+j]=f[0][ls][lw]+1,b.push((node){rs+i,rw+j,1});
}
else {
int ls=x-t.s,lw=y-t.w,rs=t.s,rw=t.w;
if (rs-i<0||ls+i>x||rw-j<0||lw+j>y) continue;
if (rs-i+q<rw-j&&rs-i!=0) continue;
if (f[0][ls+i][lw+j]>f[1][rs][rw]+1) f[0][ls+i][lw+j]=f[1][rs][rw]+1,b.push((node){ls+i,lw+j,0});
}
}
}
}
return ;
}
signed main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
/*ios::sync_with_stdio(false);
cout.tie(0);cin.tie(0);*/
cin>>x>>y>>p>>q;
for (int i=0;i<=200;i++)
for (int j=0;j<=200;j++) f[0][i][j]=f[1][i][j]=1e9;
f[0][x][y]=0;f[1][0][0]=0;bfs();
int ans=1e9;
for (int i=0;i<=200;i++) {
//if (f[1][x][i]<ans) cout<<i<<endl;
ans=min(ans,f[1][x][i]);
}
if (ans==1e9) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4244kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4256kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4480kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4260kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4492kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4196kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 1ms
memory: 4200kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 1ms
memory: 4260kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 6ms
memory: 4256kb
input:
60 60 8 1
output:
27
result:
ok 1 number(s): "27"
Test #11:
score: 0
Accepted
time: 3ms
memory: 4260kb
input:
60 60 8 4
output:
27
result:
ok 1 number(s): "27"
Test #12:
score: 0
Accepted
time: 9ms
memory: 4264kb
input:
60 60 8 8
output:
25
result:
ok 1 number(s): "25"
Test #13:
score: 0
Accepted
time: 6ms
memory: 4432kb
input:
60 60 16 1
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 12ms
memory: 4496kb
input:
60 60 16 8
output:
11
result:
ok 1 number(s): "11"
Test #15:
score: 0
Accepted
time: 14ms
memory: 4232kb
input:
60 60 16 16
output:
11
result:
ok 1 number(s): "11"
Test #16:
score: 0
Accepted
time: 16ms
memory: 4272kb
input:
60 60 16 24
output:
9
result:
ok 1 number(s): "9"
Test #17:
score: 0
Accepted
time: 2ms
memory: 4496kb
input:
75 15 1 1
output:
175
result:
ok 1 number(s): "175"
Test #18:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
50 100 1 0
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: 0
Accepted
time: 43ms
memory: 4304kb
input:
100 100 10 10
output:
35
result:
ok 1 number(s): "35"
Test #20:
score: 0
Accepted
time: 28ms
memory: 4492kb
input:
100 100 10 1
output:
37
result:
ok 1 number(s): "37"
Test #21:
score: 0
Accepted
time: 66ms
memory: 4264kb
input:
100 100 10 20
output:
33
result:
ok 1 number(s): "33"
Test #22:
score: 0
Accepted
time: 81ms
memory: 4492kb
input:
100 100 10 30
output:
31
result:
ok 1 number(s): "31"
Test #23:
score: 0
Accepted
time: 124ms
memory: 4212kb
input:
100 100 10 80
output:
21
result:
ok 1 number(s): "21"
Test #24:
score: 0
Accepted
time: 124ms
memory: 4452kb
input:
100 100 1 100
output:
199
result:
ok 1 number(s): "199"
Test #25:
score: 0
Accepted
time: 16ms
memory: 4256kb
input:
100 100 5 0
output:
95
result:
ok 1 number(s): "95"
Test #26:
score: 0
Accepted
time: 59ms
memory: 4520kb
input:
100 100 25 3
output:
13
result:
ok 1 number(s): "13"
Test #27:
score: 0
Accepted
time: 67ms
memory: 4296kb
input:
100 100 30 4
output:
11
result:
ok 1 number(s): "11"
Test #28:
score: 0
Accepted
time: 11ms
memory: 4120kb
input:
95 100 3 3
output:
125
result:
ok 1 number(s): "125"
Test #29:
score: 0
Accepted
time: 83ms
memory: 4212kb
input:
98 99 50 6
output:
5
result:
ok 1 number(s): "5"
Test #30:
score: 0
Accepted
time: 80ms
memory: 4260kb
input:
100 100 45 4
output:
7
result:
ok 1 number(s): "7"
Test #31:
score: 0
Accepted
time: 124ms
memory: 4532kb
input:
100 100 40 39
output:
7
result:
ok 1 number(s): "7"
Test #32:
score: 0
Accepted
time: 120ms
memory: 4324kb
input:
100 100 45 19
output:
7
result:
ok 1 number(s): "7"
Test #33:
score: 0
Accepted
time: 162ms
memory: 4416kb
input:
100 100 49 99
output:
5
result:
ok 1 number(s): "5"
Test #34:
score: 0
Accepted
time: 159ms
memory: 4312kb
input:
100 100 49 100
output:
5
result:
ok 1 number(s): "5"
Test #35:
score: 0
Accepted
time: 162ms
memory: 4316kb
input:
100 100 49 98
output:
5
result:
ok 1 number(s): "5"
Test #36:
score: 0
Accepted
time: 169ms
memory: 4408kb
input:
100 100 49 97
output:
5
result:
ok 1 number(s): "5"
Test #37:
score: 0
Accepted
time: 161ms
memory: 4408kb
input:
100 100 49 96
output:
5
result:
ok 1 number(s): "5"
Test #38:
score: 0
Accepted
time: 165ms
memory: 4380kb
input:
100 100 49 95
output:
5
result:
ok 1 number(s): "5"
Test #39:
score: 0
Accepted
time: 128ms
memory: 4352kb
input:
100 100 100 0
output:
1
result:
ok 1 number(s): "1"
Test #40:
score: 0
Accepted
time: 1ms
memory: 4200kb
input:
1 100 1 0
output:
1
result:
ok 1 number(s): "1"
Test #41:
score: 0
Accepted
time: 13ms
memory: 4140kb
input:
90 100 5 5
output:
87
result:
ok 1 number(s): "87"
Test #42:
score: 0
Accepted
time: 1ms
memory: 4260kb
input:
100 1 1 0
output:
199
result:
ok 1 number(s): "199"
Test #43:
score: 0
Accepted
time: 45ms
memory: 4520kb
input:
94 61 22 35
output:
9
result:
ok 1 number(s): "9"
Test #44:
score: 0
Accepted
time: 18ms
memory: 4188kb
input:
61 92 36 6
output:
7
result:
ok 1 number(s): "7"
Test #45:
score: 0
Accepted
time: 7ms
memory: 4452kb
input:
73 89 12 4
output:
57
result:
ok 1 number(s): "57"
Test #46:
score: 0
Accepted
time: 1ms
memory: 4448kb
input:
71 80 4 3
output:
-1
result:
ok 1 number(s): "-1"
Test #47:
score: 0
Accepted
time: 8ms
memory: 4488kb
input:
44 75 2 31
output:
85
result:
ok 1 number(s): "85"
Test #48:
score: 0
Accepted
time: 7ms
memory: 4460kb
input:
48 62 5 18
output:
35
result:
ok 1 number(s): "35"
Test #49:
score: 0
Accepted
time: 56ms
memory: 4228kb
input:
73 100 22 49
output:
9
result:
ok 1 number(s): "9"
Extra Test:
score: 0
Extra Test Passed