Pagini recente » Cod sursa (job #1863863) | Cod sursa (job #236587) | Cod sursa (job #1519178) | Cod sursa (job #2921887) | Cod sursa (job #71310)
Cod sursa(job #71310)
using namespace std;
#define MAX_N 50005
#include <stdio.h>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#define Vmax 5000005
int n,i;
long long s,dif,val=-1,sp;
long long a[MAX_N];
char p[MAX_N],semn;
int pls[Vmax],mns[Vmax];
int main()
{
FILE *fin=fopen("semne.in","r"),
*fout=fopen("semne.out","w");
fscanf(fin,"%d %lld\n",&n,&s);
memset(p,0,sizeof(p));
for (i=1; i<=n; i++)
{
fscanf(fin,"%lld",a+i);
sp+=a[i]; p[i]=1;
pls[a[i]]++;
}
srand ( time(NULL) );
int c=n;
while(sp>s)
{
sp-= (a[c]<<1);
p[c]=0;
pls[a[c]]--;
mns[a[c]]++;
c--;
}
dif=s-sp;
if(dif%2==0)
{
dif/=2;
if(dif>0 && dif<=5000000 && mns[dif]>0)
{
val=dif;
semn=0;
}
if(dif<0 && dif>=-5000000 && pls[-dif]>0)
{
val=-dif;
semn=1;
}
}
while (sp!=s && val<0)
{
c=rand();
if(c>33000) return 0;
c%=n;
p[c]^=1;
if(p[c])
{
sp+=(a[c]<<1);
pls[a[c]]++;
mns[a[c]]--;
}
else
{
sp-=(a[c]<<1);
pls[a[c]]--;
mns[a[c]]++;
}
dif=s-sp;
if(dif%2==0)
{
dif/=2;
if(dif>0 && dif<=5000000 && mns[dif]>0)
{
val=dif;
semn=0;
break;
}
if(dif<0 && dif>=-5000000 && pls[-dif]>0)
{
val=-dif;
semn=1;
break;
}
}
}
for (i=1; i<=n; i++)
if(a[i] == val && p[i] == semn)
{
p[i]^=1;
val=-1;
i--;
}
else
if (p[i]==1) fprintf(fout,"+");
else fprintf(fout,"-");
fclose(fin); fclose(fout);
return 0;
}