Cod sursa(job #538)

Utilizator mariusdrgdragus marius mariusdrg Data 11 decembrie 2006 14:56:18
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include<stdio.h>
#include<algorithm>


using namespace std;

const int maxn = 50010;

int j;
int x;
long long a[maxn];
long long i;
int ver[maxn];
long long k;
long long n,s1;
long long s;
long long c[maxn];
long long l1;
long long aux;
long long l2;
long long b[maxn];



long long bs(long long val)
{
        long long i,p,x=0;
        for(p=1;p<=n;p<<=1);
        for(;p;p>>=1)
                if(c[x+p]<=val&&x+p<=n) x+=p;
        for(x=x;x>0;x--)
                if (ver[x]==0)break;
        if (c[x]==val)return x;
        return 0;

}

int main()
{
        freopen("semne.in","r",stdin);
        freopen("semne.out","w",stdout);
        scanf("%lld %lld",&n,&s1);
        for(i=1;i<=n;i++)
        {
                scanf("%lld",&a[i]);
                c[i]=a[i];
                s+=a[i];
        }
        l1=n;
        long long s2=0;
        while (s-s2!=s1)
        {
                if (s-s2>s1)
                {
                        i=rand()%l1+1;
                        s-=a[i];
                        aux=a[l1];
                        a[l1]=a[i];
                        a[i]=aux;
                        l1--;
                        l2++;
                        b[l2]=a[l1+1];
                        s2+=a[l1+1];
                        a[l1+1]=0;
                }
                else
                {
                        i=rand()%l2+1;
                        s2-=b[i];
                        aux=b[l2];
                        b[l2]=b[i];
                        b[i]=aux;
                        l2--;
                        l1++;
                        a[l1]=b[l2+1];
                        s+=b[l2+1];
                        b[l2+1]=0;
                }
                
        }
        for(j=1;j<=l1;j++)
        {
                ver[bs(a[j])]=1;
        }
        for(i=1;i<=n;i++)
                if (ver[i])   printf("+");
                        else printf("-");
        return 0;
}