QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#807071 | #9873. Last Chance: Threads of Despair | Pessimism | TL | 0ms | 3620kb | C++23 | 6.1kb | 2024-12-09 18:37:49 | 2024-12-09 18:37:54 |
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]);
}
for (int i = 0; i < n; i++) {
if (h[i] == 1) {
if (!first) {
attack++;
}
has = true;
first = true;
cnt++;
}
}
for (int i = 0; i < n; i++) {
if (h[i] != 1) {
if (attack < sum) {
attack++;
my.push(h[i] - 1);
} else {
my.push(h[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: 100
Accepted
time: 0ms
memory: 3620kb
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: -100
Time Limit Exceeded
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