fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fi first
  4. #define se second
  5. #define str string
  6. #define pu push
  7. #define pb push_back
  8. #define pii pair<long long,long long>
  9. #define __MaCodVN__ signed main()
  10. #define task "TroChoiTrenBang"
  11.  
  12. const ll N=2e5+9;
  13. const ll mxN= 1e6+9;
  14. const ll mod=1e9+7;
  15. const int AC=0;
  16.  
  17. using namespace std;
  18. ll n,tt,m,a[N],b[N];
  19. map<ll,ll> d;
  20.  
  21. bool check (ll x)
  22. {
  23.  //cout<<x<<" "<<d[x]<<'\n';   
  24.  if(x==0 || (x==1 && d[x]==0))
  25.   return false;   
  26.  if(d[x])
  27.   return true;
  28.  else
  29.   {
  30.    if(x%2==0)
  31.     {
  32.      if(check(x/2))
  33.       {
  34.        d[x/2]--;
  35.        if(check(x/2))
  36.         {
  37.          d[x/2]--;
  38.          d[x]++;
  39.          return true;
  40.         } 
  41.        d[x/2]++;
  42.        return false; 
  43.       }  
  44.      return false;  
  45.     }
  46.    else
  47.     {
  48.      if(check(x/2))
  49.       {
  50.        d[x/2]--;
  51.        if(check(x/2+1))
  52.         {
  53.          d[x/2+1]--;
  54.          d[x]++;
  55.          return true;
  56.         } 
  57.        d[x/2]++;
  58.        return false; 
  59.       }  
  60.      return false;  
  61.     }
  62.   }    
  63. }
  64.  
  65. void meme1()
  66. {
  67.  priority_queue<ll> q;
  68.  for(ll i=1;i<=n;i++){
  69.   d[a[i]]++;
  70.   //resa+=a[i];
  71.  } 
  72.  for(ll i=1;i<=m;i++){
  73.   q.push(b[i]);
  74.   //resb+=b[i];
  75.  }
  76.  ll cnt=0; 
  77.  while(q.size())
  78.   {
  79.    ll x=q.top();
  80.    q.pop();
  81.  
  82.    auto it=d.find(x);
  83.    if(it!= d.end() && it -> second>0)
  84.     {
  85.      it -> second--;
  86.      if(it -> second ==0)
  87.       d.erase(it);
  88.      continue;    
  89.     }
  90.    if(x==1)
  91.     {
  92.      cout<<"No"<<'\n';
  93.      return;   
  94.     } 
  95.    ll u=x/2;
  96.    ll v=x-u;
  97.    q.push(u);
  98.    q.push(v); 
  99.   }
  100.  if(!q.size()) 
  101.   cout<<"Yes"<<'\n';
  102.  else
  103.   cout<<"No"<<'\n'; 
  104. }
  105.  
  106. void meme2()
  107. {
  108.  for(ll i=1;i<=n;i++)
  109.    d[a[i]]++; 
  110.  sort(a+1,a+1+n);
  111.  sort(b+1,b+1+m);   
  112.  ll ok=0;
  113.  //cout<<check(9)<<'\n';
  114.  
  115.  for(ll i=1;i<=m;i++)
  116.   {
  117.    if(d[b[i]])
  118.     d[b[i]]--;
  119.    else
  120.     {  
  121.      if(check(b[i]))
  122.        continue;
  123.      else
  124.       {
  125.        cout<<"No"<<'\n'; 
  126.        ok=1;
  127.        break;
  128.       }     
  129.     }  
  130.   }
  131.  if(ok==0)
  132.   {
  133.    for(ll i=1;i<=n;i++)
  134.     if(d[a[i]])
  135.      {
  136.       cout<<"No"<<'\n';
  137.       ok=1;
  138.       break;  
  139.      }
  140.    if(ok==0)
  141.     cout<<"Yes"<<'\n';   
  142.   }   
  143. }
  144.  
  145. void solve ()
  146. {
  147.  d.clear();   
  148.  cin>>n>>m;
  149.  ll resa=0,resb=0;   
  150.  for(ll i=1;i<=n;i++){
  151.   cin>>a[i];
  152.   resa+=a[i];
  153.  } 
  154.  for(ll i=1;i<=m;i++){
  155.   cin>>b[i]; 
  156.   resb+=b[i];
  157.  } 
  158. //  if(n==m)
  159. //   meme1();
  160. //  else 
  161. //   meme2();  
  162.  if(resa!=resb)
  163.   cout<<"No"<<'\n';
  164.  else 
  165.   meme1(); 
  166.  //meme1();
  167. }
  168.  
  169. __MaCodVN__
  170. {
  171.  ios_base::sync_with_stdio(false);
  172.  cin.tie(NULL);cout.tie(NULL);
  173.  if(fopen(task".INP", "r")) {
  174.   freopen(task".INP", "r", stdin);
  175.   freopen(task".OUT", "w", stdout);
  176.  }
  177.  cin>>tt;
  178.  while(tt--)
  179.   solve();
  180.  return AC;
  181. }
  182.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jUNNW1
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!