QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#821094 | #9873. Last Chance: Threads of Despair | qsmcgogo# | WA | 2ms | 7660kb | C++20 | 3.4kb | 2024-12-19 13:00:52 | 2024-12-19 13:00:53 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
int a[1110110],b[1101010],c[1100110],d[202020];
vector<int>g[202020];
pair<int,int>p[202020];
int dp[5050];
int mi;
map<pair<int,int>,int>mp;
signed main(){
// ios::sync_with_stdio(false);cin.tie(0);
// cout<<acos(1)<<" "<<acos(-1)<<'\n';
int _=1;
cin>>_;
int i,j;
int n;
while(_--){
int n,m,l,k,w;
cin>>n>>m;
map<int,int>mp;
multiset<int>s1,s2,sb;
int c=0;
for(i=0;i<n;i++)cin>>a[i],mp[a[i]]++;
for(i=0;i<m;i++)cin>>b[i],sb.insert(b[i]),mp[b[i]]++;
set<int>no;
sort(a,a+n);
for(i=0;i<n;i++){
if(a[i]>1&&mp[a[i]-1]==0){
c++;
mp[a[i]-1]++;
mp[a[i]]--;
// s1.erase(s1.find(a[i]));
}
else {
if(mp[a[i]]==1)s1.insert(a[i]);
else s2.insert(a[i]);
}
}
int ma=(*sb.rbegin());
for(i=1;i<=n+m;i++){
// cout<<i<<" "<<mp[i]<<'\n';
if(mp[i]==0)no.insert(i);
}
// for(auto i:s1)cout<<i<<" ";
// cout<<'\n';
// for(auto i:s2)cout<<i<<" ";
// cout<<'\n';
// for(auto i:no)cout<<i<<" ";
// cout<<'\n';
while(no.size()&&ma>(*no.begin())){
auto temp=sb.lower_bound(*no.begin());
// cout<<(*temp)<<" "<<(*no.begin())<<'\n';
if(c>=(*temp)-(*no.begin())){
c-=(*temp)-(*no.begin());
mp[(*temp)]--;
mp[(*no.begin())]++;
no.erase(no.begin());
sb.erase(sb.find(*temp));
sb.insert(*no.begin());
if(!mp[*temp])no.insert(*temp);
if(mp[*temp]==1){
if(s2.count(*temp)){
s2.erase(*temp);
s1.insert(*temp);
}
}
}
else{
cout<<(*temp)<<" "<<(*no.begin())<<" "<<c<<'\n';
int x=*temp;
if(mp[x]==2&&s2.count(x)){
s2.erase(x);
s1.insert(x);
}
x-=c;
c=0;
while(x>(*no.begin())&&s2.size()){
int y=(*s2.begin());
if(mp[y]==1){
s2.erase(y);
s1.insert(y);
continue;
}
s2.erase(s2.find(y));
mp[y]--;
mp[y-1]++;
if(s1.count(y-1)){
s1.erase(y-1);
s2.insert(y-1);
}
x--;
}
while(x>(*no.begin())&&s1.size()){
int y=(*s1.rbegin());
s1.erase(s1.find(y));
mp[y]--;
mp[y-1]++;
if(mp[y]==0)no.insert(y);
if(no.count(y-1))no.erase(y-1);
x--;
}
mp[(*temp)]--;
mp[x]++;
sb.insert(x);
sb.erase(sb.find(*temp));
ma=(*sb.rbegin());
if(!mp[*temp])no.insert(*temp);
if(no.count(x))no.erase(x);
if(!c&&!s1.size()&&!s2.size())break;
}
}
// cout<<ma<<" "<<(*no.begin())<<'\n';
if(ma>(*no.begin()))cout<<"No\n";
else cout<<"Yes\n";
}
}
/*
1
5 3
1 4 4 5 5
5 6 7
1
3 1
1 2 3
6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7660kb
input:
3 3 2 1 1 4 2 6 3 2 1 1 4 2 7 2 1 100 100 2
output:
6 4 1 Yes 7 4 1 No Yes
result:
wrong output format YES or NO expected, but 6 found [1st token]