Cod sursa(job #1562164)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 4 ianuarie 2016 20:58:29
Problema Farfurii Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <stdio.h>
#include <stdlib.h>
int poz[100001],rez[100001],cost[100001];
int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}
void quicksort(int p,int u,int vr[],int b[])
{
    int pivot,j,i,aux;
    if(p<u)
    {
        pivot=vr[(p+u)/2];
        i=p;
        j=u;
        while(i<=j)
        {
            while(vr[i]<pivot && i<u)
                i++;
            while(vr[j]>pivot && j>p)
                j--;
            if(i<=j){
                aux=vr[i];
                vr[i]=vr[j];
                vr[j]=aux;
                aux=b[i];
                b[i]=b[j];
                b[j]=aux;
                i++;
                j--;
            }
        }
        if(p<j)
            quicksort(p,j,vr,b);
        if(i<u)
            quicksort(i,u,vr,b);
    }
}
int main()
{
    int n,k,z,i,p,j;
    freopen("farfurii.in","r",stdin);
    freopen("farfurii.out","w",stdout);
    scanf("%d%d",&n,&k);
    z=0;
    for(i=n; i>=1; i--)
    {
        cost[i]=min(k,z);
        k-=min(k,z);
        z++;
        poz[i]=i;
    }
    quicksort(1,n,cost,poz);
    for(i=1; i<=n;)
    {
        j=i+1;
        while(j<=n && cost[i]==cost[j])
            j++;
        quicksort(i,j-1,poz,cost);
        i=j;
    }
    for(i=1; i<=n; i++)
        rez[poz[i]]=i;
    for(i=1; i<=n; i++)
        printf("%d ",rez[i]);

    return 0;
}