QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744621#7781. Sheep Eat WolvescoolarecRE 120ms22352kbC++202.1kb2024-11-13 22:38:162024-11-13 22:38:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 22:38:17]
  • 评测
  • 测评结果:RE
  • 用时:120ms
  • 内存:22352kb
  • [2024-11-13 22:38:16]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,p,q;
int cnt=0;
int id[105][105][2];
int getid(int x,int y,int op)
{
    if(!id[x][y][op]) id[x][y][op]=++cnt;
    return id[x][y][op];
}
void solve()
{
    cin>>n>>m>>p>>q;
    vector<int> e[101*101*2];
    for(int i=0;i<=n;i++)//i j 都是左
    {
        for(int j=0;j<=m;j++)
        {
            // if(j-i>p && i!=0) continue;
            if((m-j)-(n-i)>q && n-i!=0) continue;
            for(int k=0;k<=n;k++)//k l 都是右
            {
                for(int l=0;l<=m;l++)
                {
                    // if(i+k!=n || j+l!=m) continue;
                    // if(l-k>q && l!=0) continue;
                    // if((m-l)-(n-k)>p && n-k!=0) continue;
                    int sheep=k-(n-i),wolf=l-(m-j);//船上羊的数量 狼的数量
                    // if(i==4 && j==4 && k==2 && l==1) cout<<sheep<<' '<<wolf<<endl;
                    if(sheep<0 || wolf<0) continue;
                    if(sheep+wolf>p) continue;
                    if(j-wolf-(i-sheep)>q && i-sheep!=0) continue;
                    // cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
                    // if(i==4 && j==4) cout<<k<<' '<<l<<endl;
                    e[getid(i,j,0)].push_back(getid(k,l,1));
                    e[getid(i,j,1)].push_back(getid(k,l,0));
                }
            }
        }
    }
    queue<int> q;
    q.push(getid(n,m,0));
    vector<int> dis(101*101*2);
    dis[getid(n,m,0)]=1;
    while(q.size())
    {
        auto u=q.front();q.pop();
        // cout<<x<<' '<<y<<' '<<op<<endl;
        // cout<<u<<endl;
        for(auto v:e[u])
        {
            if(dis[v]) continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    int ans=1e18;
    for(int i=0;i<=m;i++)
    {
        int tmp=dis[getid(n,i,1)];
        // cout<<n<<' '<<i<<' '<<tmp<<endl;
        if(tmp) ans=min(tmp,ans);
    }
    if(ans==1e18) cout<<-1<<endl;
    else cout<<ans-1<<endl;
}
signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    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: 4044kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4348kb

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 4100kb

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

score: 0
Accepted
time: 1ms
memory: 4004kb

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 4368kb

input:

10 9 1 10

output:

19

result:

ok 1 number(s): "19"

Test #8:

score: 0
Accepted
time: 1ms
memory: 4140kb

input:

15 20 2 5

output:

27

result:

ok 1 number(s): "27"

Test #9:

score: 0
Accepted
time: 0ms
memory: 4192kb

input:

18 40 16 7

output:

5

result:

ok 1 number(s): "5"

Test #10:

score: 0
Accepted
time: 9ms
memory: 4476kb

input:

60 60 8 1

output:

27

result:

ok 1 number(s): "27"

Test #11:

score: 0
Accepted
time: 10ms
memory: 4848kb

input:

60 60 8 4

output:

27

result:

ok 1 number(s): "27"

Test #12:

score: 0
Accepted
time: 7ms
memory: 5240kb

input:

60 60 8 8

output:

25

result:

ok 1 number(s): "25"

Test #13:

score: 0
Accepted
time: 10ms
memory: 5676kb

input:

60 60 16 1

output:

13

result:

ok 1 number(s): "13"

Test #14:

score: 0
Accepted
time: 13ms
memory: 7872kb

input:

60 60 16 8

output:

11

result:

ok 1 number(s): "11"

Test #15:

score: 0
Accepted
time: 17ms
memory: 10440kb

input:

60 60 16 16

output:

11

result:

ok 1 number(s): "11"

Test #16:

score: 0
Accepted
time: 21ms
memory: 12560kb

input:

60 60 16 24

output:

9

result:

ok 1 number(s): "9"

Test #17:

score: 0
Accepted
time: 2ms
memory: 4476kb

input:

75 15 1 1

output:

175

result:

ok 1 number(s): "175"

Test #18:

score: 0
Accepted
time: 5ms
memory: 4156kb

input:

50 100 1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 64ms
memory: 7904kb

input:

100 100 10 10

output:

35

result:

ok 1 number(s): "35"

Test #20:

score: 0
Accepted
time: 57ms
memory: 5116kb

input:

100 100 10 1

output:

37

result:

ok 1 number(s): "37"

Test #21:

score: 0
Accepted
time: 80ms
memory: 11420kb

input:

100 100 10 20

output:

33

result:

ok 1 number(s): "33"

Test #22:

score: 0
Accepted
time: 85ms
memory: 14072kb

input:

100 100 10 30

output:

31

result:

ok 1 number(s): "31"

Test #23:

score: 0
Accepted
time: 120ms
memory: 22352kb

input:

100 100 10 80

output:

21

result:

ok 1 number(s): "21"

Test #24:

score: -100
Runtime Error

input:

100 100 1 100

output:


result: