QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#821094#9873. Last Chance: Threads of Despairqsmcgogo#WA 2ms7660kbC++203.4kb2024-12-19 13:00:522024-12-19 13:00:53

Judging History

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

  • [2024-12-19 13:00:53]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7660kb
  • [2024-12-19 13:00:52]
  • 提交

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]