Cod sursa(job #2107625)

Utilizator madalin98Gherghe Madalin madalin98 Data 17 ianuarie 2018 16:31:06
Problema Sortare prin comparare Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.68 kb
#include<fstream>
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
int v[500005],a[500005],vs[500005];
int build(int nod,int l,int r)
{
    int mid=(l+r)/2;
    if(r==l){
        a[nod]=v[l];
        return v[l];
    }
    int val1=build(2*nod,l,mid);
    int val2=build(2*nod+1,mid+1,r);
    if(val1>val2)a[nod]=val1;
       else a[nod]=val2;
    return a[nod];
}
void update(int pos,int x,int nod,int l,int r)
{
    int mid=(l+r)/2;
    if(r==l){
        a[nod]=x;
        v[l]=x;
    }
    else{
        if(pos<=mid)update(pos,x,2*nod,l,mid);
            else update(pos,x,2*nod+1,mid+1,r);
        if(a[2*nod]>a[2*nod+1])a[nod]=a[2*nod];
          else a[nod]=a[2*nod+1];
    }
}
int query(int st_q,int dr_q,int nod,int l,int r)
{
    int mid=(l+r)/2;
    if(st_q>r||l>dr_q)return 0;
	if(st_q<=l&&r<=dr_q)return a[nod];
    int val1=query(st_q,dr_q,2*nod,l,mid);
    int val2=query(st_q,dr_q,2*nod+1,mid+1,r);
    if(val1>val2)return val1;
      else return val2;
}
int caut(int x,int n)
{
    for(int i=1;i<=n;i++)
        if(v[i]==x)return i;
}
int main()
{
    int n,i,x,p;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    build(1,1,n);
    int k=0;
    for(i=1;i<=n;i++)
        {
        x=query(1,n,1,1,n);
        vs[++k]=x;
        p=caut(x,n);
        update(p,0,1,1,n);
        }
    for(i=k;i>=1;i--)
        g<<vs[i]<<" ";
    return 0;
}
/*int v[200001],a[200001];
int build(int nod,int l,int r)
{
    int mid=(l+r)/2;
    if(r==l){
        a[nod]=v[l];
        return v[l];
    }
    int val1=build(2*nod,l,mid);
    int val2=build(2*nod+1,mid+1,r);
    if(val1>val2)a[nod]=val1;
       else a[nod]=val2;
    return a[nod];
}
void update(int pos,int x,int nod,int l,int r)
{
    int mid=(l+r)/2;
    if(r==l){
        a[nod]=x;
        v[l]=x;
    }
    else{
        if(pos<=mid)update(pos,x,2*nod,l,mid);
            else update(pos,x,2*nod+1,mid+1,r);
        if(a[2*nod]>a[2*nod+1])a[nod]=a[2*nod];
          else a[nod]=a[2*nod+1];
    }
}
int query(int st_q,int dr_q,int nod,int l,int r)
{
    int mid=(l+r)/2;
    if(st_q>r||l>dr_q)return 0;
	if(st_q<=l&&r<=dr_q)return a[nod];
    int val1=query(st_q,dr_q,2*nod,l,mid);
    int val2=query(st_q,dr_q,2*nod+1,mid+1,r);
    if(val1>val2)return val1;
      else return val2;
}
int cauta(int st,int dr,int x)
{
    for(int i=st;i<=dr;i++)
        if(v[i]==x)return i;
}
int main()
{
    int n,i,x,p;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    build(1,1,n);
    for(i=1;i<=n;i++)
    {
        x=query(1,n,1,1,n);
        g<<x<<" ";
        p=cauta(1,n,x);
        update(p,0,1,1,n);
    }
    return 0;
}*/