Source Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define s second
#define f first
#define pb push_back
int a[200005],b[200005],n,m;
int idx[400005];
int ans[200005];
int vis[200005];
set<int>st;
int dp[200005][3];
int best,best2,besti,best2i;
int fun(int idx,int last)
{
    if(idx==m)
        return 0;
    int &ret=dp[idx][last];
    if(~ret)
        return ret;
    if(~ans[idx])
    {
       if(a[ans[idx]-1]==best) return ret=fun(idx+1,1);
       if(a[ans[idx]-1]==best2) return ret=fun(idx+1,0);
       return ret=fun(idx+1,2);
    }
    if(last==2)
    {
        int op1=(best>b[idx])+fun(idx+1,0);
        int op2=(best2>b[idx])+fun(idx+1,1);
        return ret=max(op1,op2);
    }
    if(last==1)
    {
        return ret=(best>b[idx])+fun(idx+1,0);
    }
    return ret=(best2>b[idx])+fun(idx+1,1);
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        st.clear();
       cin>>n>>m;
       for(int i=0;i<n;i++)
       {
           cin>>a[i];
           idx[a[i]]=i+1;
       }
       for(int i=0;i<m;i++)
       {
           vis[i]=0;
           ans[i]=-1;
           dp[i][0]=dp[i][1]=dp[i][2]=-1;
           cin>>b[i];
           idx[b[i]]=i+1;
           st.insert(b[i]);
       }
       dp[m][0]=dp[m][1]=dp[m][2]=-1;
       sort(a,a+n);
       best=a[n-1];
       best2=a[n-2];
       besti=idx[best];
       best2i=idx[best2];
       int cnt=0;
       for(int i=n-1;i>=0;i--)
       {
           auto ii=st.lower_bound(a[i]);
           if(ii==st.begin())
           {
               ii=st.end();
               cnt--;
           }
           ii--;
           cnt++;
           ans[idx[(*ii)]-1]=idx[a[i]];
           st.erase(ii);
       }
       int lastt=2;
       for(int i=0;i<m;i++)
       {
           if(~ans[i])
           {
               if(a[ans[i]-1]==best) lastt=1;
               else if(a[ans[i]-1]==best2) lastt=0;
               else lastt=2;
               continue;
           }
           if(lastt==2)
           {
            int op1=(best>b[i])+fun(i+1,0);
            int op2=(best2>b[i])+fun(i+1,1);
            if(op1>=op2)
            {
                ans[i]=besti;
                lastt=0;
            }
            else
            {
                ans[i]=best2i;
                lastt=1;
            }
            continue;
           }
           if(lastt==1)
           {
               ans[i]=best2i;
               lastt=0;
               continue;
           }
           ans[i]=besti;
           lastt=1;
       }
      cnt+=fun(0,2);
       cout<<cnt<<endl;
       for(int i=0;i<m;i++)
        cout<<ans[i]<<" \n"[i+1==m];
    }
    return 0;
}
Copy
Ayoub vs Mahmoud ahmedfouadnew
GNU G++17
0 ms
360 KB
Wrong Answer