Merge without extra space

PHOTO EMBED

Mon Aug 30 2021 07:18:58 GMT+0000 (UTC)

Saved by @zs #c++

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define ull unsigned long long
using namespace std;
void merge(int *arr1,int *arr2,int n, int m){
    int i=0,j=0,k=0;
    int maxi=INT_MIN;
    rep(i,0,n) maxi=max(arr1[i],maxi);
    rep(i,0,m) maxi=max(arr2[i],maxi);
    maxi++;
    while(i<n && j<m){
        int x=arr1[i]%maxi;
        int y=arr2[j]%maxi;
        if(x<y){
            if(k<n)  arr1[k]+=x*maxi;
            else  arr2[k-n]+=x*maxi;
            k++;
            i++;
        }
        else{
            if(k<n)  arr1[k]+=y*maxi;
            else arr2[k-n]+=y*maxi;
            k++;
            j++;
        }
    }
    while(i<n){
        int x=arr1[i]%maxi;
        if(k<n) arr1[k]+=x*maxi;
        else arr2[k-n]+=x*maxi;
        k++;
        i++;
    }
    while(j<m){
        int x=arr2[j]%maxi;
        if(k<n) arr1[k]+=x*maxi;
        else  arr2[k-n]+=x*maxi;
        k++;
        j++;
    }
    rep(i,0,n) arr1[i]=arr1[i]/maxi;
    rep(i,0,m) arr2[i]=arr2[i]/maxi;
}
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        int n,m;
        cin>>n>>m;
        int *arr1=new int[n];
        int *arr2=new int[m];
        rep(i,0,n) cin>>arr1[i];
        rep(i,0,m) cin>>arr2[i];
        merge(arr1,arr2,n,m);
        rep(i,0,n) cout<<arr1[i]<<" ";
        rep(i,0,m) cout<<arr2[i]<<" ";
        cout<<endl;
    }


return 0;
}
content_copyCOPY