QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648059#7781. Sheep Eat Wolvesenar#WA 16ms5792kbC++201.6kb2024-10-17 16:49:262024-10-17 16:49:28

Judging History

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

  • [2024-10-17 16:49:28]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:5792kb
  • [2024-10-17 16:49:26]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

const int INF = 1E9;

struct Node {
    int cnt, sp, wv;
    bool operator < (const Node &u) const {
        return cnt > u.cnt;
    }
};

void solve() {
    int x, y, p, q;
    std::cin >> x >> y >> p >> q;
    std::priority_queue<Node> pq;
    std::vector vis(2, std::vector(400, std::vector<int>(400)));
    int ans = INF;
    pq.push({0, 0, 0});
    while (!pq.empty()) {
        auto [c, a, b] = pq.top();
        pq.pop();
        // std::cout << c << " " << a << " " << b << "\n";
        vis[c % 2][a][b] = 1;
        if (a == x) {
            ans = std::min(ans, c);
            continue;
        }
        if (c % 2 == 0) {
            for (int t = 1; t <= p && t <= x + y - b - a; ++t) {
                for (int i = 0; i <= x - a && i <= t; ++i) {
                    if (y - b - t + i > x - a - i + q && a + i != x) {
                        continue;
                    }
                    if (vis[(c + 1) % 2][a + i][std::min(y - b, b + t - i)]) continue;
                    pq.push({c + 1, a + i, std::min(y - b, b + t - i)});
                }
            }
        } else {
            for (int i = 0; i <= b && i <= p; ++i) {
                if (b - i > a + q && a != 0) continue;
                if (vis[(c + 1) % 2][a][b - i]) continue;
                pq.push({c + 1, a, b - i});
            }
        }
    }
    if (ans == INF) ans = -1;
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while(T--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4896kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

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

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

10 9 1 10

output:

19

result:

ok 1 number(s): "19"

Test #8:

score: -100
Wrong Answer
time: 16ms
memory: 5792kb

input:

15 20 2 5

output:

-1

result:

wrong answer 1st numbers differ - expected: '27', found: '-1'