Two Array Problem
Problem Statement :
In this problem you operate on two arrays of integers. We will call them the and the respectively. Your goal is just to maintain them under the modification operations, such as: 1 : Reverse the subarray of the array, starting at the number, ending at the number, inclusively; 2 : Swap two consecutive fragments of the array, the first is from the number to the , the second is from the number to the ; 3 : Swap the piece that starts at the number and end at the one between the and the array; 4 : We consider only the piece from the number to the one. The numbers in the array are -coordinates of some set of points and the numbers in the array are -coordinates of them. For the obtained set of points we would like to place such a circle on a plane that would contain all the points in it and would have the minimal radius. Find this minimal radius. Input Format The first line of input contains two space separated integers and denoting the number of integers in arrays and the number of queries respectively. The second line contains space separated integers: the initial elements of the array. The third line contains space separated integers: the initial elements of the array. Then there are lines containing queries in the format listed above. Output Format For each type-4 query output the sought minimal radius with exactly two symbols after the decimal point precision. Constraints 1 <= N, M <= 10^5
Solution :
Solution in C :
In C++ :
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
void RI() {}
template<typename... T>
void RI( int& head, T&... tail ) {
scanf("%d",&head);
RI(tail...);
}
// }}}
const int INF=0x7FFFFFFF;
const int N=400010;
const double eps=1e-6;
struct P { double x,y; } p[N],q[3];
double dis2( P a, P b ) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); }
P operator -( P a, P b ) { return (P){a.x-b.x,a.y-b.y}; }
P operator +( P a, P b ) { return (P){a.x+b.x,a.y+b.y}; }
P operator /( P a, double b ) { return (P){a.x/b,a.y/b}; }
double abs2( P a ) { return a.x*a.x+a.y*a.y; }
double dot( P a, P b ) { return a.x*b.x+a.y*b.y; }
double X( P a, P b ) { return a.x*b.y-a.y*b.x; }
double X( P a, P b, P c ) { return X(b-a,c-a); }
struct C {
P o; double r2;
C() { o.x=o.y=r2=0; }
C( P a ) { o=a; r2=0; }
C( P a, P b ) { o=(a+b)/2; r2=dis2(o,a); }
C( P a, P b, P c ) {
double i,j,k,A=2*X(a,b,c)*X(a,b,c);
i=abs2(b-c)*dot(a-b,a-c);
j=abs2(a-c)*dot(b-a,b-c);
k=abs2(a-b)*dot(c-a,c-b);
o.x=(i*a.x+j*b.x+k*c.x)/A;
o.y=(i*a.y+j*b.y+k*c.y)/A;
r2=dis2(o,a);
}
bool cover( P a ) { return dis2(o,a)<=r2+eps; }
};
C MEC( int n, int m ) {
C mec;
if ( m==1 ) mec=C(q[0]);
else if ( m==2 ) mec=C(q[0],q[1]);
else if ( m==3 ) return C(q[0],q[1],q[2]);
for ( int i=0; i<n; i++ )
if ( !mec.cover(p[i]) ) {
q[m]=p[i];
mec=MEC(i,m+1);
}
return mec;
}
int my_rand() {
static int seed;
return seed=seed*1103515245+12345;
}
struct Treap {
static Treap mem[N],*pmem;
Treap *l,*r;
int rnd,size,val;
bool rev;
Treap() {}
Treap( int _val ):l(NULL),r(NULL),rnd(rand()),size(1),val(_val),rev(false) {}
} Treap::mem[N],*Treap::pmem=Treap::mem;
inline int size( Treap *t ) { return t?t->size:0; }
inline void push( Treap *t ) {
if ( !t ) return;
if ( t->rev ) {
if ( t->l ) t->l->rev^=1;
if ( t->r ) t->r->rev^=1;
swap(t->l,t->r);
t->rev=false;
}
}
inline void pull( Treap *t ) {
if ( !t ) return;
t->size=size(t->l)+size(t->r)+1;
}
Treap* merge( Treap *a, Treap *b ) {
if ( !a || !b ) return a?a:b;
if ( a->rnd < b->rnd ) {
push(a);
a->r=merge(a->r,b);
pull(a);
return a;
} else {
push(b);
b->l=merge(a,b->l);
pull(b);
return b;
}
}
void split( Treap *t, int k, Treap *&a, Treap *&b ) {
push(t);
if ( !t ) a=b=NULL;
else if ( k<=size(t->l) ) {
b=t;
split(t->l,k,a,b->l);
pull(b);
} else {
a=t;
split(t->r,k-size(t->l)-1,a->r,b);
pull(a);
}
}
void go( Treap *t, vector<int> &v ) {
if ( !t ) return;
push(t);
go(t->l,v);
v.PB(t->val);
go(t->r,v);
}
Treap* input( int n ) {
Treap *t=NULL;
REP1(i,1,n) {
int x;
RI(x);
t=merge(t,new (Treap::pmem++) Treap(x));
}
return t;
}
Treap *t[2];
int main() {
srand(time(0)^getpid()^514514514);
int n,m;
RI(n,m);
REP(i,2) t[i]=input(n);
while ( m-- ) {
int op;
RI(op);
if ( op==1 ) {
int id,l,r;
RI(id,l,r);
Treap *tl,*tr;
split(t[id],l-1,tl,t[id]);
split(t[id],r-l+1,t[id],tr);
t[id]->rev^=1;
t[id]=merge(merge(tl,t[id]),tr);
} else if ( op==2 ) {
int id,l1,r1,l2,r2;
RI(id,l1,r1,l2,r2);
Treap *t1,*t2,*t3,*t4,*t5;
split(t[id],l1-1,t1,t[id]);
split(t[id],r1-l1+1,t2,t[id]);
split(t[id],l2-r1-1,t3,t[id]);
split(t[id],r2-l2+1,t4,t5);
t[id]=merge(merge(merge(merge(t1,t4),t3),t2),t5);
} else if ( op==3 ) {
int l,r;
RI(l,r);
Treap *tl[2],*tm[2],*tr[2];
REP(i,2) {
split(t[i],l-1,tl[i],t[i]);
split(t[i],r-l+1,tm[i],tr[i]);
}
t[0]=merge(merge(tl[0],tm[1]),tr[0]);
t[1]=merge(merge(tl[1],tm[0]),tr[1]);
} else if ( op==4 ) {
int l,r;
RI(l,r);
vector<int> v[2];
REP(i,2) {
Treap *tl,*tr;
split(t[i],l-1,tl,t[i]);
split(t[i],r-l+1,t[i],tr);
go(t[i],v[i]);
t[i]=merge(merge(tl,t[i]),tr);
}
assert(v[0].size() == v[1].size());
int vn=SZ(v[0]);
REP(i,vn) {
p[i].x=v[0][i];
p[i].y=v[1][i];
}
random_shuffle(p,p+vn);
C c=MEC(vn,0);
double ans=sqrt(c.r2);
printf("%.2f\n",ans);
}
}
return 0;
}
In Java :
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Random;
import java.util.StringTokenizer;
public class TwoArrayProblem {
static int MAX = 1111111;
static class Node {
Node child[] = new Node[2], parent;
boolean reverse;
int value, size;
}
static class SplayTree {
public static final Node nil;
static {
nil = new Node();
nil.child[0] = nil.child[1] = nil.parent = nil;
nil.reverse = false;
nil.value = nil.size = 0;
}
private Node root = nil;
public SplayTree(int a[]) {
root = buildTree(a, 0, a.length - 1);
}
private Node buildTree(int a[], int l, int r) {
if (l > r) return nil;
int mid = (l + r) >> 1;
Node x = new Node();
x.value = a[mid];
x.parent = nil;
x.reverse = false;
setLink(x, buildTree(a, l, mid - 1), 0);
setLink(x, buildTree(a, mid + 1, r), 1);
update(x);
return x;
}
private void update(Node x) {
x.size = x.child[0].size + x.child[1].size + 1;
}
private void pushDown(Node x) {
if (x != nil) {
if (x.reverse) {
Node tmp = x.child[0];
x.child[0] = x.child[1];
x.child[1] = tmp;
x.reverse = false;
x.child[0].reverse = !x.child[0].reverse;
x.child[1].reverse = !x.child[1].reverse;
}
}
}
private static void setLink(Node parent,
Node child, int d) {
parent.child[d] = child;
child.parent = parent;
}
private int getDir(Node parent, Node child) {
return parent.child[0] == child ? 0 : 1;
}
private void rotate(Node x, int d) {
Node y = x.child[d], z = x.parent;
setLink(x, y.child[d ^ 1], d);
setLink(y, x, d ^ 1);
setLink(z, y, getDir(z, x));
update(x);
update(y);
}
private void splay(Node x) {
while (x.parent != nil) {
Node y = x.parent, z = y.parent;
int dy = getDir(y, x), dz = getDir(z, y);
if (z == nil) rotate(y, dy);
else if (dy == dz) {
rotate(z, dz);
rotate(y, dy);
} else {
rotate(y, dy);
rotate(z, dz);
}
}
root = x;
}
public void reverse(int right) {
if (right <= 1) return;
if (right == root.size) root.reverse = !root.reverse;
else {
accessByPos(right + 1);
root.child[0].reverse = !root.child[0].reverse;
}
}
public void reverse(int left, int right) {
if (left >= right) return;
reverse(right);
reverse(right - left + 1);
reverse(right);
}
public void swap(int left1, int right1,
int left2, int right2) {
reverse(left1, right1);
reverse(left2, right2);
reverse(right1 + 1, left2 - 1);
reverse(left1, right2);
}
private void dfs(Node root, int[] buffer) {
if (root == nil) return;
pushDown(root);
dfs(root.child[0], buffer);
buffer[++buffer[0]] = root.value;
dfs(root.child[1], buffer);
}
public void collect(int left, int right, int[] buffer) {
buffer[0] = 0;
if (left == 1 && right == root.size) {
dfs(root, buffer);
} else {
reverse(right);
Node x = accessByPos(right - left + 2).child[0];
dfs(x, buffer);
reverse(right);
}
}
public Node accessByPos(int pos) {
assert (pos >= 1 && pos <= root.size);
Node x = root;
pushDown(x);
while (x.child[0].size + 1 != pos) {
if (pos < x.child[0].size + 1) x = x.child[0];
else {
pos -= x.child[0].size + 1;
x = x.child[1];
}
pushDown(x);
}
splay(x);
return x;
}
}
static int n, m;
static int[] a;
static int[] buffer2 = new int[MAX];
static int[] buffer1 = new int[MAX];
static Random rand = new Random();
static double[][] p = new double[MAX][2];
static final double eps = 1E-8;
static double dis(double[] a, double[] b) {
return Math.sqrt((a[0] - b[0]) * (
a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));
}
static void circumcenter(double[] a,
double[] b, double[] c, double[] res) {
double a1 = b[0] - a[0], b1 = b[1] - a[1],
c1 = (a1 * a1 + b1 * b1) / 2;
double a2 = c[0] - a[0], b2 = c[1] - a[1],
c2 = (a2 * a2 + b2 * b2) / 2;
double d = a1 * b2 - a2 * b1;
res[0] = a[0] + (c1 * b2 - c2 * b1) / d;
res[1] = a[1] + (a1 * c2 - a2 * c1) / d;
}
static double minDisk(int[] x, int[] y) {
// randomly permute them
for (int n = x[0]; n >= 1; n--) {
int i = rand.nextInt(n) + 1;
int tmp = x[i];
x[i] = x[n];
x[n] = tmp;
tmp = y[i];
y[i] = y[n];
y[n] = tmp;
}
for (int i = 1; i <= x[0]; i++) {
p[i][0] = x[i];
p[i][1] = y[i];
}
double[] c = p[1].clone();
double r = 0;
for (int i = 2; i <= x[0]; i++) {
if (dis(p[i], c) > r + eps) // ????
{
c[0] = p[i][0];
c[1] = p[i][1];
r = 0;
for (int j = 1; j < i; j++)
if (dis(p[j], c) > r + eps) // ????
{
c[0] = (p[i][0] + p[j][0]) / 2;
c[1] = (p[i][1] + p[j][1]) / 2;
r = dis(p[j], c);
for (int k = 1; k < j; k++)
if (dis(p[k], c) > r + eps) // ????
{// ?????????????
circumcenter(p[i], p[j], p[k], c);
r = dis(p[i], c);
}
}
}
}
return r;
}
public static void main(String[] args)
throws Exception {
BufferedReader cin = new BufferedReader(
new InputStreamReader(System.in));
BufferedWriter cout = new BufferedWriter(
new OutputStreamWriter(System.out));
StringTokenizer token =
new StringTokenizer(cin.readLine());
n = Integer.parseInt(token.nextToken());
m = Integer.parseInt(token.nextToken());
a = new int[2 * n];
int index = 0;
token = new StringTokenizer(cin.readLine());
for (int i = 0; i < n; i++) {
a[index++] = Integer.parseInt(token.nextToken());
}
token = new StringTokenizer(cin.readLine());
for (int i = 0; i < n; i++) {
a[index++] = Integer.parseInt(token.nextToken());
}
SplayTree tree = new SplayTree(a);
for (; m > 0; m--) {
token = new StringTokenizer(cin.readLine());
int op = Integer.parseInt(token.nextToken());
if (op == 1) {
int id = Integer.parseInt(token.nextToken());
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
if (id == 1) {
left += n;
right += n;
}
tree.reverse(left, right);
} else if (op == 2) {
int id = Integer.parseInt(token.nextToken());
int left1 = Integer.parseInt(token.nextToken());
int right1 = Integer.parseInt(token.nextToken());
int left2 = Integer.parseInt(token.nextToken());
int right2 = Integer.parseInt(token.nextToken());
if (id == 1) {
left1 += n;
right1 += n;
left2 += n;
right2 += n;
}
tree.swap(left1, right1, left2, right2);
} else if (op == 3) {
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
tree.swap(left, right, left + n, right + n);
} else if (op == 4) {
int left = Integer.parseInt(token.nextToken());
int right = Integer.parseInt(token.nextToken());
tree.collect(left, right, buffer1);
tree.collect(left + n, right + n, buffer2);
double r = minDisk(buffer1, buffer2);
cout.write(String.format("%.2f%n", r));
}
}
cin.close();
cout.close();
}
}
In C :
#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("%.2lf\n",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;
}
View More Similar Problems
Simple Text Editor
In this challenge, you must implement a simple text editor. Initially, your editor contains an empty string, S. You must perform Q operations of the following 4 types: 1. append(W) - Append W string to the end of S. 2 . delete( k ) - Delete the last k characters of S. 3 .print( k ) - Print the kth character of S. 4 . undo( ) - Undo the last (not previously undone) operation of type 1 or 2,
View Solution →Poisonous Plants
There are a number of plants in a garden. Each of the plants has been treated with some amount of pesticide. After each day, if any plant has more pesticide than the plant on its left, being weaker than the left one, it dies. You are given the initial values of the pesticide in each of the plants. Determine the number of days after which no plant dies, i.e. the time after which there is no plan
View Solution →AND xor OR
Given an array of distinct elements. Let and be the smallest and the next smallest element in the interval where . . where , are the bitwise operators , and respectively. Your task is to find the maximum possible value of . Input Format First line contains integer N. Second line contains N integers, representing elements of the array A[] . Output Format Print the value
View Solution →Waiter
You are a waiter at a party. There is a pile of numbered plates. Create an empty answers array. At each iteration, i, remove each plate from the top of the stack in order. Determine if the number on the plate is evenly divisible ith the prime number. If it is, stack it in pile Bi. Otherwise, stack it in stack Ai. Store the values Bi in from top to bottom in answers. In the next iteration, do the
View Solution →Queue using Two Stacks
A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed. A basic que
View Solution →Castle on the Grid
You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):
View Solution →