QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#820736#9873. Last Chance: Threads of DespairTreeQwQWA 0ms3620kbC++201.6kb2024-12-19 00:18:332024-12-19 00:18:34

Judging History

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

  • [2024-12-19 00:18:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3620kb
  • [2024-12-19 00:18:33]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n + 1), b(m + 1);
  int one = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    one += (a[i] == 1);
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
  }

  int dmg = (one > 0 ? n - one + 1 : n);

  int aoe = (one > 0);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
  bool fst = true;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 1 && fst) {
      fst = false;
    } else {
      q.push({max(a[i] - 1, 1), 0});
    }
  }
  for (int i = 1; i <= m; i++) {
    q.push({b[i], 1});
  }
  while (!q.empty()) {
    auto [x, id] = q.top();
    if (aoe >= x) {
      aoe++;
      q.pop();
    } else {
      break;
    }
  }

  priority_queue<int, vector<int>, greater<>> q1, q2;
  while (!q.empty()) {
    auto [x, id] = q.top();
    q.pop();
    if (id == 0) {
      q1.push(x);
    } else {
      q2.push(x);
    }
  }

  while (!q2.empty() && dmg > 0) {
    int x = q2.top();
    if (x <= aoe) {
      q2.pop();
      aoe++;
    } else if (x - aoe <= dmg) {
      dmg -= (x - aoe);
      aoe++;
      q2.pop();
    } else {
      cout << "No\n";
      return;
    }
    while (!q1.empty()) {
      int y = q1.top();
      if (aoe >= y) {
        aoe++;
        q1.pop();
      } else {
        break;
      }
    }
  }

  cout << "Yes\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int tc;
  cin >> tc;
  while (tc--) {
    solve();
  }

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3592kb

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: 3620kb

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: -100
Wrong Answer
time: 0ms
memory: 3480kb

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
Yes
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No

result:

wrong answer expected NO, found YES [5th token]