QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#807056 | #9873. Last Chance: Threads of Despair | Pessimism | WA | 0ms | 3644kb | C++23 | 5.6kb | 2024-12-09 18:33:36 | 2024-12-09 18:33:37 |
Judging History
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 {
attack++;
my.push(h[i] - 1);
}
}
int sum = 0;
for (int i = 0; i < m; i++) {
cin >> g[i];
// sum += g[i];
emy.push(g[i]);
}
while (!emy.empty()) {
if (!has) {
while (!emy.empty() && emy.top() > 1 && !my.empty()) {
auto top = emy.top();
emy.pop();
emy.push(top - 1);
used.push(my.top() - 1);
my.pop();
}
if (!emy.empty() && emy.top() <= 1) {
if (!my.empty()) {
// assert(attack == 0);
has = true;
first = true;
cnt++;
used.push(my.top() - 1);
my.pop();
emy.pop();
} else {
cout << "NO\n";
return;
}
} else {
cout << "NO\n";
return;
}
} else {
if (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
} else if (!my.empty() && my.top() <= cnt) {
attack++;
cnt++;
my.pop();
} else if (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
} else {
// while (!emy.empty() && emy.top() > cnt && !my.empty()) {
// used.push(my.top() - 1);
// while (!used.empty() && used.top() <= cnt) {
// cnt++;
// used.pop();
// }
// attack++;
// my.pop();
// if (emy.top() <= cnt) {
// attack++;
// break;
// }
// auto top = emy.top();
// emy.pop();
// emy.push(top - 1);
// }
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
// while (!emy.empty() && emy.top() > cnt && attack > 0) {
// auto top = emy.top();
// emy.pop();
// emy.push(top - 1);
// attack--;
// }
if (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
} else {
if (my.empty()) {
break;
}
}
}
}
}
assert(my.empty() || emy.empty());
assert(has);
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
while (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
}
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
while (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
}
// cout << attack << endl;
// cout << emy.size() << endl;
while (!emy.empty() && attack > 0) {
while (true) {
int p = cnt;
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
while (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
}
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
while (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
}
if (p == cnt) {
break;
}
}
if (emy.empty()) {
break;
}
auto top = emy.top();
emy.pop();
emy.push(top - 1);
attack--;
}
// cout << emy.size() << endl;
while (true) {
int p = cnt;
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
while (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
}
while (!used.empty() && used.top() <= cnt) {
cnt++;
used.pop();
}
while (!emy.empty() && emy.top() <= cnt) {
cnt++;
emy.pop();
}
if (p == cnt) {
break;
}
}
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3644kb
input:
3 3 2 1 1 4 2 6 3 2 1 1 4 2 7 2 1 100 100 2
output:
YES YES YES
result:
wrong answer expected NO, found YES [2nd token]