Pagini recente » Cod sursa (job #1275866) | Cod sursa (job #547751) | Cod sursa (job #1720397) | Cod sursa (job #1776488) | Cod sursa (job #50898)
Cod sursa(job #50898)
#include <stdio.h>
#include <time.h>
#define Nmax 50002
#define key 1234566691
typedef long long lint;
lint MOD = 1<<31;
lint a[Nmax], b[Nmax], v[Nmax];
lint r, p;
char s[Nmax];
void srand(lint seed)
{
r = 1+seed;
}
inline lint rand()
{
r+=key;
if(r>MOD)
r -= MOD;
return r;
}
int main()
{
freopen("semne.in","r",stdin);
freopen("semne.out","w",stdout);
lint i,n,S=0, A=0,B=0;
srand((lint)time(0));
scanf("%d%d", &n,&S);
for(i=1;i<=n;++i)
{
scanf("%d", v+i);
if(A - B <= S)
{
a[++a[0]] = i;
A += v[i];
s[i] = '+';
}
else
{
b[++b[0]] = i;
B += v[i];
s[i] = '-';
}
}
while(A-B != S)
{
if(A-B > S)
{
// mut din A in B
int tmp = (rand()%a[0])+1;
b[++b[0]] = a[tmp];
A -= v[a[tmp]];
B += v[a[tmp]];
s[a[tmp]] = '-';
a[tmp] = a[a[0]--];
}
if(A-B < S)
{
// mut din B in A
int tmp = (rand()%b[0])+1;
a[++a[0]] = b[tmp];
A += v[b[tmp]];
B -= v[b[tmp]];
s[b[tmp]] = '+';
b[tmp] = b[b[0]--];
}
if(b[0] == 0 && A-B != S)
{
// mut din A in B
int tmp = (rand()%a[0])+1;
b[++b[0]] = a[tmp];
A -= v[a[tmp]];
B += v[a[tmp]];
s[a[tmp]] = '-';
a[tmp] = a[a[0]--];
}
if(a[0] == 0 && A-B != S)
{
// mut din B in A
int tmp = (rand()%b[0])+1;
a[++a[0]] = b[tmp];
A += v[b[tmp]];
B -= v[b[tmp]];
s[b[tmp]] = '+';
b[tmp] = b[b[0]--];
}
}
for(i=1;i<=n;++i)
printf("%c", s[i]);
return 0;
}