Pagini recente » Cod sursa (job #2766723) | Borderou de evaluare (job #2960147) | Cod sursa (job #2160065) | Cod sursa (job #2836523) | Cod sursa (job #791304)
Cod sursa(job #791304)
#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;
}