Cod sursa(job #791304)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 23 septembrie 2012 19:16:59
Problema Semne Scor 95
Compilator cpp Status done
Runda asem-info Marime 1.75 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 50010;
int j,x;
long long a[maxn],i,ver[maxn],k,n,s1,s,c[maxn],l1,aux,l2,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;
}