HackerRank Two Array Problem solution YASH PAL, 31 July 2024 In this HackerRank Two Array Problem solution, we are given two arrays of N integers. we need to perform some modification operations on that.Problem solution in Java Programming.import java.io.*; import java.util.*; public class Solution { static class Vec { double x, y; Vec() { } Vec(double x, double y) { this.x = x; this.y = y; } Vec add(Vec q) { return new Vec(x + q.x, y + q.y); } Vec minus(Vec q) { return new Vec(x - q.x, y - q.y); } Vec mult(double t) { return new Vec(x * t, y * t); } Vec div(double t) { return new Vec(x / t, y / t); } double mult(Vec q) { return x * q.x + y * q.y; } double modulo(Vec q) { return x * q.y - y * q.x; } } static final int N = 100000; static final int V = (N + 2) * 2; static Vec[] a; static double hypot(double x, double y) { return Math.sqrt(x * x + y * y); } static double abs(Vec p) { return hypot(p.x, p.y); } static class Circle { double x, y, r; Circle(double x, double y, double r) { this.x = x; this.y = y; this.r = r; } Circle(Vec a, double r) { this.x = a.x; this.y = a.y; this.r = r; } } static boolean inCircle(Circle c, Vec a) { return hypot(a.x - c.x, a.y - c.y) <= c.r; } static Vec circumcenter(Vec p, Vec q, Vec r) { Vec a = p.minus(r); Vec b = q.minus(r); Vec c = new Vec(a.mult(p.add(r)) / 2, b.mult(q.add(r)) / 2); Vec x = new Vec(a.x, b.x); Vec tmp = new Vec(c.modulo(new Vec(a.y, b.y)), x.modulo(c)); return tmp.div(a.modulo(b)); } static Circle smallestEnclosingCircle(int n) { Circle C = new Circle(0, 0, -1); for (int i = 0; i < n; i++) { if (!inCircle(C, a[i])) { C = new Circle(a[i], 0); for (int j = 0; j < i; j++) { if (!inCircle(C, a[j])) { C = new Circle((a[i].add(a[j])).div(2), abs(a[i].minus(a[j])) / 2); for (int k = 0; k < j; k++) { if (!inCircle(C, a[k])) { Vec o = circumcenter(a[i], a[j], a[k]); C = new Circle(o, abs(o.minus(a[k]))); } } } } } } return C; } static int[] y = new int[N]; static int ny; static class Node { boolean flp; Node l, r; int key, size; void init(int k, int s) { flp = false; key = k; size = s; l = r = nodeNull; } int cmp(int k) { if (l.size == k) { return -1; } return l.size < k ? 1 : 0; } void mconcat() { size = l.size + 1 + r.size; } void untag() { if (flp) { flp = false; l.flip(); r.flip(); } } void flip() { if (this == nodeNull) { return; } Node tmp = l; l = r; r = tmp; flp = !flp; } } static Node[] pool = new Node[V]; static int allo = 0; static Node nodeNull = new Node(); static Node splay(Node x, int k) { Node lspine = nodeNull; Node rspine = nodeNull; for (;;) { x.untag(); if (x.l.size == k) { break; } if (x.l.size < k) { k -= x.l.size + 1; Node y = x.r; y.untag(); if (x.r.cmp(k) == 1) { k -= x.r.l.size + 1; x.r = y.l; y.l = x; x.mconcat(); x = y.r; y.r = lspine; lspine = y; } else { x.r = lspine; lspine = x; x = y; } } else { Node y = x.l; y.untag(); if (x.l.cmp(k) == 0) { x.l = y.r; y.r = x; x.mconcat(); x = y.l; y.l = rspine; rspine = y; } else { x.l = rspine; rspine = x; x = y; } } } { Node z = x.l; while (lspine != nodeNull) { Node y = lspine.r; lspine.r = z; lspine.mconcat(); z = lspine; lspine = y; } x.l = z; } { Node z = x.r; while (rspine != nodeNull) { Node y = rspine.l; rspine.l = z; rspine.mconcat(); z = rspine; rspine = y; } x.r = z; } x.mconcat(); return x; } static Node range(Node rt, int L, int R) { rt = splay(rt, L - 1); rt.r = splay(rt.r, R - L); return rt; } static void inorder(Node rt, int d) { if (rt != nodeNull) { rt.untag(); inorder(rt.l, d + 1); y[ny++] = rt.key; inorder(rt.r, d + 1); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for (int i = 0; i < pool.length; i++) { pool[i] = new Node(); } a = new Vec[n]; for (int i = 0; i < a.length; i++) { a[i] = new Vec(); } Node[] rt = { pool[allo++], pool[allo++] }; nodeNull.init(0, 0); for (int d = 0; d < 2; d++) { rt[d].init(-1, 1); st = new StringTokenizer(br.readLine()); for (int i = 0; i <= n; i++) { Node node = pool[allo]; if (i < n) { int item = Integer.parseInt(st.nextToken()); node.init(item, i + 2); } else { node.init(-1, i + 2); } node.l = rt[d]; rt[d] = pool[allo++]; } } while (m-- > 0) { st = new StringTokenizer(br.readLine()); int query = Integer.parseInt(st.nextToken()); int l0, r0, id; Node p = null, q = null; switch (query) { case 1: id = Integer.parseInt(st.nextToken()); l0 = Integer.parseInt(st.nextToken()); r0 = Integer.parseInt(st.nextToken()); rt[id] = range(rt[id], l0, r0 + 1); rt[id].r.l.flip(); break; case 2: id = Integer.parseInt(st.nextToken()); l0 = Integer.parseInt(st.nextToken()); r0 = Integer.parseInt(st.nextToken()); int l1 = Integer.parseInt(st.nextToken()); int r1 = Integer.parseInt(st.nextToken()); if (r0 + 1 == l1) { rt[id] = range(rt[id], l0, r0 + 1); rt[id].r.l.flip(); rt[id] = range(rt[id], l1, r1 + 1); rt[id].r.l.flip(); rt[id] = range(rt[id], l0, r1 + 1); rt[id].r.l.flip(); } else { rt[id] = range(rt[id], l1, r1 + 1); q = rt[id].r.l; rt[id].r.l = nodeNull; rt[id].r.mconcat(); rt[id].mconcat(); rt[id] = range(rt[id], l0, r0 + 1); p = rt[id].r.l; rt[id].r.l = q; rt[id].r.mconcat(); rt[id].mconcat(); int s = l1 + (r1 - r0) - (l1 - l0); rt[id] = range(rt[id], s, s); rt[id].r.l = p; rt[id].r.mconcat(); rt[id].mconcat(); } break; case 3: l0 = Integer.parseInt(st.nextToken()); r0 = Integer.parseInt(st.nextToken()); rt[0] = range(rt[0], l0, r0 + 1); p = rt[0].r.l; rt[1] = range(rt[1], l0, r0 + 1); q = rt[1].r.l; rt[0].r.l = q; rt[0].r.mconcat(); rt[0].mconcat(); rt[1].r.l = p; rt[1].r.mconcat(); rt[1].mconcat(); break; case 4: l0 = Integer.parseInt(st.nextToken()); r0 = Integer.parseInt(st.nextToken()); ny = 0; rt[0] = range(rt[0], l0, r0 + 1); p = rt[0].r.l; inorder(p, 0); id = ny; for (int i = 0; i < id; i++) { a[i].x = y[i]; } ny = 0; rt[1] = range(rt[1], l0, r0 + 1); q = rt[1].r.l; inorder(q, 0); for (int i = 0; i < id; i++) { a[i].y = y[i]; } double result = smallestEnclosingCircle(id).r; bw.write(String.format("%.2fn", result)); break; default: break; } } bw.newLine(); bw.close(); br.close(); } }Problem solution in C++ programming.#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cstring> #include <ctime> using namespace std; #define MAXN 200005 #define kt root->ch[1]->ch[0] const int inf = 100000; struct Node { Node *ch[2],*pre; int sz,key,rev; }; class Splay { public: void init() { cnt=0; top=0; nill=node; nill->sz=0; root=new_node(nill,-inf); root->ch[1]=new_node(root,-inf); up(root); } void insert(int pos,int num[],int l,int r) { Node *x=find_k(pos),*y=find_k(pos+1); splay(x,nill); splay(y,root); kt=make_tree(root->ch[1],num,l,r); up(root->ch[1]); up(root); } void reverse(int pos,int n) { Node *x=find_k(pos-1),*y=find_k(pos+n); splay(x,nill); splay(y,root); kt->rev^=1; up(root->ch[1]); up(root); } void cut(int pos1, int n1, int pos2, int n2) { Node *x = find_k(pos1 - 1), *y = find_k(pos1 + n1); splay(x, nill); splay(y, root); Node *c1 = kt; kt = nill; up(root->ch[1]); up(root); x = find_k(pos2 - n1 - 1); y = find_k(pos2 - n1 + n2); splay(x, nill); splay(y, root); Node *c2 = kt; kt = c1; c1->pre = root->ch[1]; up(root->ch[1]); up(root); x = find_k(pos1 - 1); y = find_k(pos1); splay(x, nill); splay(y, root); kt = c2; c2->pre = root->ch[1]; up(root->ch[1]); up(root); } void takeNum(int *a, int pos, int n) { Node *x = find_k(pos - 1), *y = find_k(pos + n); splay(x, nill); splay(y, root); int sz = 0; make_array(a, sz, kt); } private: int cnt,top; Node node[MAXN],*mem[MAXN],*root,*nill,*stack[MAXN]; void up(Node *x) { x->sz=1+x->ch[0]->sz+x->ch[1]->sz; } void down(Node *x) { if(x->rev) { x->rev=0; x->ch[0]->rev^=1; x->ch[1]->rev^=1; swap(x->ch[0],x->ch[1]); } } Node *new_node(Node *f,int v)//??????v?????f { Node *x; if(top) x=mem[--top]; else x=&node[++cnt]; x->key=v; x->sz=1; x->rev=0; x->pre=f; x->ch[0]=x->ch[1]=nill; return x; } void rotate(Node *x,int f) { Node *y=x->pre; //down(y); // down(x); y->ch[!f]=x->ch[f]; x->ch[f]->pre=y; x->pre=y->pre; if(y->pre!=nill) y->pre->ch[y->pre->ch[1]==y]=x; x->ch[f]=y; y->pre=x; up(y); } void splay(Node *x,Node *to)//?x???to??? { int tot=0; Node *tmp=x; while(true) { stack[tot++]=tmp; tmp=tmp->pre; if(tmp==nill) break; } for(int i=tot-1;i>=0;i--) down(stack[i]); while(x->pre!=to) { if(x->pre->pre==to) rotate(x,x->pre->ch[0]==x); else { Node *y=x->pre,*z=y->pre; int f=(z->ch[0]==y); if(y->ch[f]==x) rotate(x,!f),rotate(x,f); else rotate(y,f),rotate(x,f); } } up(x); if(to==nill) root=x; } Node *find_k(int k)//?????k??? { Node *x=root; while(true) { down(x); if(x->ch[0]->sz==k) return x; if(x->ch[0]->sz>k) x=x->ch[0]; else { k-=(1+x->ch[0]->sz); x=x->ch[1]; } } } Node *make_tree(Node *f,int num[],int l,int r) { if(r<l) return nill; int mid=(l+r)/2; Node *x=new_node(f,num[mid]); x->ch[0]=make_tree(x,num,l,mid-1); x->ch[1]=make_tree(x,num,mid+1,r); up(x); return x; } void make_array(int *a, int &sz, Node *x) { if (x == nill) return; down(x); make_array(a, sz, x->ch[0]); a[sz ++] = x->key; make_array(a, sz, x->ch[1]); } void clear(Node *x)//???? { if(x==nill) return; mem[top++]=x; clear(x->ch[0]); clear(x->ch[1]); } }; Splay splay; int num[MAXN],n,m; int px[MAXN], py[MAXN]; const double EPS = 1e-8; int sgn(double x) { if (fabs(x)<=EPS) return 0; return x>0?1:-1; } struct point { double x,y; point(): x(0),y(0) {} point(double a,double b): x(a),y(b) {} point operator + (const point &b) const { return point(x+b.x,y+b.y); } point operator - (const point &b) const { return point(x-b.x,y-b.y); } double operator * (const point &b) const { return x*b.y-y*b.x; } double dis(const point &b) const { return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)); } }; struct hplane { point s,t; point cross (const hplane &b) const { point p=b.t-s; double s1=(b.t-s)*(b.s-s); double s2=(b.s-t)*(b.t-t); return point((s.x*s2+t.x*s1)/(s2+s1),(s.y*s2+t.y*s1)/(s2+s1)); } }; point p[MAXN],cen; double calCircle(int *px, int *py, int n) { for (int i = 0; i < n; i ++) { p[i].x = px[i]; p[i].y = py[i]; } srand(time(0)); random_shuffle(p, p + n); cen = p[0]; double r = 0; for (int i=1;i<n;i++) if (sgn(cen.dis(p[i])-r)>0) { cen=p[i]; r=0; for (int j=0;j<i;j++) if (sgn(cen.dis(p[j])-r)>0) { cen=point((p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0); r=p[i].dis(p[j])/2.0; for (int k=0;k<j;k++) if (sgn(cen.dis(p[k])-r)>0) { hplane l1,l2; l1.s=point((p[i].x+p[j].x)/2.0,(p[i].y+p[j].y)/2.0); l1.t=l1.s+point(p[i].y-p[j].y,p[j].x-p[i].x); l2.s=point((p[i].x+p[k].x)/2.0,(p[i].y+p[k].y)/2.0); l2.t=l2.s+point(p[i].y-p[k].y,p[k].x-p[i].x); cen=l1.cross(l2); r=cen.dis(p[i]); } } } return r; } int main() { int n, m; scanf("%d%d", &n, &m); splay.init(); for (int i = 1; i <= n * 2; i ++) { scanf("%d", num + i); } splay.insert(0, num, 1, n * 2); for (int i = 0; i < m; i ++) { int ope; scanf("%d", &ope); if (ope == 1) { int id, l, r; scanf("%d%d%d", &id, &l, &r); if (id == 0) { splay.reverse(l, r - l + 1); } else { splay.reverse(l + n, r - l + 1); } } else if (ope == 2) { int id, l1, r1, l2, r2; scanf("%d%d%d%d%d", &id, &l1, &r1, &l2, &r2); if (id == 0) { splay.cut(l1, r1 - l1 + 1, l2, r2 - l2 + 1); } else { splay.cut(l1 + n, r1 - l1 + 1, l2 + n, r2 - l2 + 1); } } else if (ope == 3) { int l, r; scanf("%d%d", &l, &r); splay.cut(l, r - l + 1, l + n, r - l + 1); } else { int l, r; scanf("%d%d", &l, &r); splay.takeNum(px, l, r - l + 1); splay.takeNum(py, l + n, r - l + 1); printf("%.2fn", calCircle(px, py, r - l + 1)); } } return 0; } Problem solution in C programming.#include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct _ct_node{ int size; int priority; int value; int reverse; struct _ct_node *left,*right; } ct_node; long long cross(long long Ox,long long Oy, long long Ax,long long Ay,long long Bx,long long By); double get_r(int x1,int y1,int x2,int y2,int x3,int y3); int inside(int x,int y); void sed(int idx,int r_size,int x1,int x2, int x3,int y1,int y2,int y3); double solve(); void tra(ct_node *root,int *A); ct_node* merge(ct_node *L,ct_node *R); int sizeOf(ct_node *root); void recalc(ct_node *root); void split(int x,ct_node **L,ct_node **R,ct_node *root); void push(ct_node *root); ct_node* reverse(int A,int B,ct_node *root); void computeTree(); int get_size(ct_node *root); void sort_a2(int*a,int*b,int size); void merge2(int*a,int*left_a,int*right_a,int*b, int*left_b,int*right_b,int left_size, int right_size); int P[100000],st[100000],T[100000],a[100000], b[100000],h1[100000],h2[100000],N,NN; double pi,CX,CY,R; ct_node poll[200000],*root[2]; int main(){ int M,x,l1,l2,r1,r2,i; ct_node *p1,*p2,*p3,*p4,*p5,*p6; pi=atan(1)*4; scanf("%d%d",&N,&M); for(i=0;i<N;i++){ scanf("%d",&poll[i].value); poll[i].priority=P[i]=rand(); poll[i].reverse=0; poll[i].left=poll[i].right=NULL; } computeTree(); for(i=0;i<N;i++) if(T[i]==-1) root[0]=&poll[i]; else if(i<T[i]) poll[T[i]].left=&poll[i]; else poll[T[i]].right=&poll[i]; get_size(root[0]); for(i=0;i<N;i++){ scanf("%d",&poll[i+N].value); poll[i+N].priority=P[i]=rand(); poll[i+N].reverse=0; poll[i+N].left=poll[i+N].right=NULL; } computeTree(); for(i=0;i<N;i++) if(T[i]==-1) root[1]=&poll[i+N]; else if(i<T[i]) poll[T[i]+N].left=&poll[i+N]; else poll[T[i]+N].right=&poll[i+N]; get_size(root[1]); while(M--){ scanf("%d",&x); switch(x){ case 1: scanf("%d%d%d",&x,&l1,&r1); root[x]=reverse(l1-1,r1-1,root[x]); break; case 2: scanf("%d%d%d%d%d",&x,&l1,&r1,&l2,&r2); split(r2-1,&p4,&p5,root[x]); split(l2-2,&p3,&p4,p4); split(r1-1,&p2,&p3,p3); split(l1-2,&p1,&p2,p2); root[x]=merge(merge(p1,p4),merge(p3,merge(p2,p5))); break; case 3: scanf("%d%d",&l1,&r1); split(r1-1,&p2,&p3,root[0]); split(l1-2,&p1,&p2,p2); split(r1-1,&p5,&p6,root[1]); split(l1-2,&p4,&p5,p5); root[0]=merge(merge(p1,p5),p3); root[1]=merge(merge(p4,p2),p6); break; default: scanf("%d%d",&l1,&r1); split(r1-1,&p2,&p3,root[0]); split(l1-2,&p1,&p2,p2); split(r1-1,&p5,&p6,root[1]); split(l1-2,&p4,&p5,p5); NN=0; tra(p2,a); NN=0; tra(p5,b); root[0]=merge(merge(p1,p2),p3); root[1]=merge(merge(p4,p5),p6); printf("%.2lfn",solve()); break; } } return 0; } long long cross(long long Ox,long long Oy, long long Ax,long long Ay,long long Bx,long long By){ return (Ax-Ox)*(By-Oy)-(Ay-Oy)*(Bx-Ox); } double get_r(int x1,int y1,int x2, int y2,int x3,int y3){ int minx,maxx; double s2,s3,mx2,my2,mx3,my3; mx2=((double)(x2+x1))/2; my2=((double)(y2+y1))/2; mx3=((double)(x3+x1))/2; my3=((double)(y3+y1))/2; if(y1==y2 && y1==y3){ CY=y1; minx=x1; if(x2<minx) minx=x2; if(x3<minx) minx=x3; maxx=x1; if(x2>maxx) maxx=x2; if(x3>maxx) maxx=x3; CX=((double)(minx+maxx))/2; return ((double)(maxx-minx))/2; } if(y1==y2){ s3=(x1-x3)/(double)(y3-y1); CX=mx2; CY=s3*CX-s3*mx3+my3; return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1)); } if(y1==y3){ s2=(x1-x2)/(double)(y2-y1); CX=mx3; CY=s2*CX-s2*mx2+my2; return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1)); } s2=(x1-x2)/(double)(y2-y1); s3=(x1-x3)/(double)(y3-y1); if(s2==s3) return 0; CX=(mx2*s2-mx3*s3-my2+my3)/(s2-s3); CY=(my3*s2-my2*s3+s2*s3*mx2-s2*s3*mx3)/(s2-s3); return sqrt((CX-x1)*(CX-x1)+(CY-y1)*(CY-y1)); } int inside(int x,int y){ return sqrt((x-CX)*(x-CX)+(y-CY)*(y-CY))<=R; } void sed(int idx,int r_size,int x1, int x2,int x3,int y1,int y2,int y3){ if(idx==NN || r_size==3){ if(r_size<=1){ R=0; CX=x1; CY=y1; } else if(r_size==2){ R=sqrt((x2-x1)*(double)(x2-x1)+(y2-y1)*( double)(y2-y1))/2; CX=((double)(x1+x2))/2; CY=((double)(y1+y2))/2; } else R=get_r(x1,y1,x2,y2,x3,y3); return; } sed(idx+1,r_size,x1,x2,x3,y1,y2,y3); if(!inside(h1[idx],h2[idx])) switch(r_size){ case 0: sed(idx+1,r_size+1,h1[idx],x2,x3,h2[idx],y2,y3); break; case 1: sed(idx+1,r_size+1,x1,h1[idx],x3,y1,h2[idx],y3); break; default: sed(idx+1,r_size+1,x1,x2,h1[idx],y1,y2,h2[idx]); } return; } double solve(){ int n=NN,k=0,t,i,j; sort_a2(a,b,NN); for(i=0;i<n;i++){ while(k>=2 && cross(h1[k-2],h2[k-2],h1[k-1],h2[k-1],a[i],b[i])<=0) k--; h1[k]=a[i]; h2[k++]=b[i]; } for(i=n-2,t=k+1;i>=0;i--){ while(k>=t && cross(h1[k-2],h2[k-2], h1[k-1],h2[k-1],a[i],b[i])<=0) k--; h1[k]=a[i]; h2[k++]=b[i]; } k--; if(k<=1) return 0; if(k==2) return sqrt((h1[0]-h1[1])*( double)(h1[0]-h1[1])+(h2[0]-h2[1])* (double)(h2[0]-h2[1]))/2; for(i=0;i<k;i++){ j=rand()%(k-i)+i; t=h1[i]; h1[i]=h1[j]; h1[j]=t; t=h2[i]; h2[i]=h2[j]; h2[j]=t; } NN=k; sed(0,0,0,0,0,0,0,0); return R; } void tra(ct_node *root,int *A){ if(!root) return; push(root); tra(root->left,A); A[NN++]=root->value; tra(root->right,A); return; } ct_node* merge(ct_node *L,ct_node *R){ if(!L) return R; if(!R) return L; if(L->priority>R->priority){ push(L); L->right=merge(L->right,R); recalc(L); return L; } push(R); R->left=merge(L,R->left); recalc(R); return R; } int sizeOf(ct_node *root){ return (root)?root->size:0; } void recalc(ct_node *root){ root->size=sizeOf(root->left)+sizeOf(root->right)+1; return; } void split(int x,ct_node **L,ct_node **R,ct_node *root){ if(!root){ *L=*R=NULL; return; } push(root); int curIndex=sizeOf(root->left); ct_node *t; if(curIndex<=x){ split(x-curIndex-1,&t,R,root->right); root->right=t; recalc(root); *L=root; } else{ split(x,L,&t,root->left); root->left=t; recalc(root); *R=root; } return; } void push(ct_node *root){ if(!root || !root->reverse) return; ct_node *t=root->left; root->left=root->right; root->right=t; root->reverse=0; if(root->left) root->left->reverse^=1; if(root->right) root->right->reverse^=1; return; } ct_node* reverse(int A,int B,ct_node *root){ ct_node *l,*m,*r; split(A-1,&l,&r,root); split(B-A,&m,&r,r); m->reverse^=1; return merge(merge(l,m),r); } void computeTree(){ int i,k,top=-1; for(i=0;i<N;i++){ k=top; while(k>=0 && P[st[k]]<P[i]) k--; if(k!=-1) T[i]=st[k]; if(k<top) T[st[k+1]]=i; st[++k]=i; top=k; } T[st[0]]=-1; return; } int get_size(ct_node *root){ if(!root) return 0; root->size=get_size(root->left)+get_size(root->right)+1; return root->size; } void sort_a2(int*a,int*b,int size){ if (size < 2) return; int m = (size+1)/2,i; int*left_a,*left_b,*right_a,*right_b; left_a=(int*)malloc(m*sizeof(int)); right_a=(int*)malloc((size-m)*sizeof(int)); left_b=(int*)malloc(m*sizeof(int)); right_b=(int*)malloc((size-m)*sizeof(int)); for(i=0;i<m;i++){ left_a[i]=a[i]; left_b[i]=b[i]; } for(i=0;i<size-m;i++){ right_a[i]=a[i+m]; right_b[i]=b[i+m]; } sort_a2(left_a,left_b,m); sort_a2(right_a,right_b,size-m); merge2(a,left_a,right_a,b,left_b,right_b,m,size-m); free(left_a); free(right_a); free(left_b); free(right_b); return; } void merge2(int*a,int*left_a,int*right_a, int*b,int*left_b,int*right_b, int left_size, int right_size){ int i = 0, j = 0; while (i < left_size|| j < right_size) { if (i == left_size) { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } else if (j == right_size) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else if (left_a[i] == right_a[j]) { if(left_b[i] < right_b[j]){ a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else{ a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } } else if (left_a[i] < right_a[j]) { a[i+j] = left_a[i]; b[i+j] = left_b[i]; i++; } else { a[i+j] = right_a[j]; b[i+j] = right_b[j]; j++; } } return; } coding problems solutions