QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#818858 | #9873. Last Chance: Threads of Despair | icealsoheat | WA | 1ms | 5868kb | C++17 | 5.9kb | 2024-12-18 10:10:54 | 2024-12-18 10:11:00 |
Judging History
answer
#pragma GCC optimize(3) //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
//inline int read() //快读
//{
// int xr=0,F=1; char cr;
// while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
// while(cr>='0'&&cr<='9')
// xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
// return xr*F;
//}
//void write(int x) //快写
//{
// if(x<0) putchar('-'),x=-x;
// if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
// int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt power(MInt a, ll b) {
MInt res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353; //这里为自动模数
using mint = MInt<P>; //mint是其定理的类型
int n,m;
int a[500005];
int b[500005];
void icealsoheat(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
int cnt=0;
sort(a+1,a+1+n);
sort(b+1,b+1+m);
int id;
id=1;
int op=0;
for(int i=n;i>=1;i--){
op++;
if(a[i]==1)break;
}
queue<int>q;
queue<int>p;
while(id<=n&&cnt>=a[id]-1){
cnt++;
id++;
}
for(int i=1;i<=m;i++){
if(op+q.size()+cnt<b[i]){
puts("No");
return;
}
op+=q.size();
if(b[i]>cnt-q.size()){
op-=b[i]-cnt+q.size();
}
int g=cnt+1;
cnt++;
while(id<=n&&cnt>=a[id]-1){
cnt++;
id++;
}
if(b[i]>cnt)q.push(b[i]);
while(q.size()){
if(q.front()<=cnt){
op+=q.front()-g;
q.pop();
}
else{
op+=q.size()*(cnt-g);
break;
}
}
}
puts("Yes");
}
signed main(){
ios::sync_with_stdio(false); //int128不能用快读!!!!!!
cin.tie();
cout.tie();
int _yq;
_yq=1;
cin>>_yq;
while(_yq--){
icealsoheat();
}
}
//
//⠀⠀⠀ ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5564kb
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: 1ms
memory: 5504kb
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: 1ms
memory: 5600kb
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: 1ms
memory: 5836kb
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: 1ms
memory: 5664kb
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
Wrong Answer
time: 1ms
memory: 5868kb
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:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes No No No No No No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No No No No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Ye...
result:
wrong answer expected NO, found YES [50th token]