QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#806418#9873. Last Chance: Threads of DespairPessimismTL 0ms3872kbC++234.5kb2024-12-09 10:32:092024-12-09 10:32:09

Judging History

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

  • [2024-12-09 10:32:09]
  • 评测
  • 测评结果：TL
  • 用时：0ms
  • 内存：3872kb
查看
  • [2024-12-09 10:32:09]
  • 提交

answer

#include<bits/stdc++.h>

#define endl "\n"
// #define int long long

using namespace std;

using i64 = long long;
using u64 = unsigned long long;

constexpr int N = 2e5 + 10, M = 2e6 + 10;
constexpr int P = 998244353;
constexpr int INF = 1e9;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> h(n), g(m);
    priority_queue<int, vector<int>, greater<>> used;
    priority_queue<int, vector<int>, greater<>> emy;
    priority_queue<int, vector<int>, greater<>> my;
    bool has = false;
    int cnt = 0;
    bool first = false;
    int attack = 0;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        if (h[i] == 1) {
            if (!first) {
                attack++;
            }
            has = true;
            first = true;
            cnt++;
        } else {
            my.push(h[i]);
        }
    }
    for (int i = 0; i < m; i++) {
        cin >> g[i];
        emy.push(g[i]);
    }
    while (((has && !my.empty()) || my.size() > 1) && !emy.empty()) {
        if (!first) {
            if (!emy.empty() && emy.top() <= 1) {
                cnt++;
                emy.pop();
            } else if (!my.empty() && my.top() <= 1) {
                cnt++;
                attack++;
                my.pop();
            } else if (!used.empty() && used.top() <= 1) {
                cnt++;
                used.pop();
            } else {
                while (emy.top() > 1 && attack > 0) {
                    auto top = emy.top();
                    emy.pop();
                    emy.push(top - 1);
                    attack--;
                }
                while (emy.top() > 1 && ((has && !my.empty()) || my.size() > 1)) {
                    auto top = emy.top();
                    emy.pop();
                    emy.push(top - 1);
                    used.push(my.top() - 1);
                    my.pop();
                    attack--;
                }
                if (emy.top() <= 1) {
                    cnt++;
                    emy.pop();
                }
            }
            first = true;
        } else {
            if (!emy.empty() && emy.top() <= cnt) {
                cnt++;
                emy.pop();
            } else if (!my.empty() && my.top() <= cnt) {
                cnt++;
                attack++;
                my.pop();
            } else if (!used.empty() && used.top() <= cnt) {
                cnt++;
                used.pop();
            } else {
                while (emy.top() > cnt && attack > 0) {
                    auto top = emy.top();
                    emy.pop();
                    emy.push(top - 1);
                    attack--;
                }
                while (emy.top() > cnt && ((has && !my.empty()) || my.size() > 1)) {
                    auto top = emy.top();
                    emy.pop();
                    emy.push(top - 1);

                    used.push(my.top() - 1);
                    my.pop();
                    attack--;
                }
                if (emy.top() <= cnt) {
                    cnt++;
                    emy.pop();
                }
            }
        }
    }
    while (!my.empty() && my.top() <= cnt) {
        cnt++;
        my.pop();
    }
    while (!used.empty() && used.top() <= cnt) {
        cnt++;
        used.pop();
    }
    while (!emy.empty() && emy.top() <= cnt) {
        cnt++;
        emy.pop();
    }
    if (!has) {
        if (!emy.empty() && emy.top() <= 1) {
            cnt++;
            emy.pop();
        }
        while (!emy.empty() && emy.top() <= cnt) {
            cnt++;
            emy.pop();
        }
        if (my.top() - 1 <= cnt) {
            cnt++;
            my.pop();
        }
        while (!emy.empty() && emy.top() <= cnt) {
            cnt++;
            emy.pop();
        }
        has = true;
    }
    while (emy.top() > cnt && attack > 0) {
        auto top = emy.top();
        emy.pop();
        emy.push(top - 1);
        attack--;
    }
    while (!my.empty() && my.top() <= cnt) {
        cnt++;
        my.pop();
    }
    while (!used.empty() && used.top() <= cnt) {
        cnt++;
        used.pop();
    }
    while (!emy.empty() && emy.top() <= cnt) {
        cnt++;
        emy.pop();
    }

    // cout << cnt << endl;
    cout << (emy.empty() && has ? "YES\n" : "NO\n");
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3872kb

input:

3
3 2
1 1 4
2 6
3 2
1 1 4
2 7
2 1
100 100
2

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

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

input:

3
7 1
1 1 1 1 1 1 1
9
5 2
3 4 5 6 7
1 6
5 3
3 4 5 6 7
1 5 7

output:

NO
NO
YES

result:

ok 3 token(s): yes count is 1, no count is 2

Test #3:

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

input:

4
1 1
1
1
1 1
1
2
1 1
2
1
1 1
2
2

output:

YES
YES
YES
NO

result:

ok 4 token(s): yes count is 3, no count is 1

Test #4:

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

input:

18
1 2
1
1 1
1 2
1
2 1
1 2
1
1 3
1 2
1
2 2
1 2
1
3 2
1 2
1
3 3
1 2
2
1 1
1 2
2
1 2
1 2
2
1 3
1 2
2
2 2
1 2
2
2 3
1 2
2
3 3
1 2
3
1 1
1 2
3
1 2
1 2
3
1 3
1 2
3
2 2
1 2
3
3 2
1 2
3
3 3

output:

YES
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO

result:

ok 18 token(s): yes count is 7, no count is 11

Test #5:

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

input:

18
2 1
1 1
1
2 1
1 1
2
2 1
1 1
3
2 1
1 2
1
2 1
2 1
2
2 1
2 1
3
2 1
1 3
1
2 1
1 3
2
2 1
3 1
3
2 1
2 2
1
2 1
2 2
2
2 1
2 2
3
2 1
2 3
1
2 1
3 2
2
2 1
2 3
3
2 1
3 3
1
2 1
3 3
2
2 1
3 3
3

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO

result:

ok 18 token(s): yes count is 15, no count is 3

Test #6:

score: -100
Time Limit Exceeded

input:

525
2 3
1 1
1 1 1
2 3
1 1
1 2 1
2 3
1 1
1 3 1
2 3
1 1
1 4 1
2 3
1 1
5 1 1
2 3
1 1
2 2 1
2 3
1 1
3 1 2
2 3
1 1
1 2 4
2 3
1 1
2 1 5
2 3
1 1
3 3 1
2 3
1 1
4 3 1
2 3
1 1
3 5 1
2 3
1 1
4 4 1
2 3
1 1
4 5 1
2 3
1 1
1 5 5
2 3
1 1
2 2 2
2 3
1 1
2 3 2
2 3
1 1
2 2 4
2 3
1 1
2 5 2
2 3
1 1
3 2 3
2 3
1 1
3 2 4
2 ...

output:

result:
English 繁體中文 简体中文

Server Time: 2025-01-28 01:20:15 | OpenSource Project