Cod sursa(job #935371)

Utilizator rudarelLup Ionut rudarel Data 3 aprilie 2013 09:30:07
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define maxn 50001
 
using namespace std;
int a[maxn], b[maxn];
int x[maxn];
int n;
long long S;
 
void afis()
{
char sol[maxn];
 
for(int i=1;i<=a[0];i++) sol[a[i]]='+';
 
for(int i=1;i<=b[0];i++) sol[b[i]]='-';
freopen("semne.out", "w", stdout);
for(int i=1;i<=n;i++) printf("%c", sol[i]);
printf("\n");
 
exit(0);
     
}
     
int sgn(int a)
{
    if(a<0) return -a;
    return a;
}
 
void solve()
{
    int i, j;
    rand();rand();
    for(i=1;i<=n;i++) if((rand())&1) a[++a[0]]=i;else b[++b[0]]=i;
     
    long long  sum=0;
    for(i=1;i<=a[0];i++) sum+=x[a[i]];
    for(i=1;i<=b[0];i++) sum-=x[b[i]];
    if(sum==S) afis();
 
    int nr=0;
    int ok=1;
    while(ok)
    {
        nr++;
        int p1;
        ok=0;
            if(sum==S) afis();
        if(sum<S && b[0]>0)
        {
             
            p1=(rand()%b[0])+1;
            {
                sum+=x[b[p1]]<<1;
                a[0]++;
                a[a[0]]=b[p1];
                b[p1]=b[b[0]];
                b[0]--;
                ok=1;
                    if(sum==S) afis();
            }
 
        }
        else if(sum>S && a[0]>0)
        {
             p1=(rand()%a[0])+1;
            {
                sum-=x[a[p1]]<<1;
                b[0]++;
                b[b[0]]=a[p1];
                a[p1]=a[a[0]];
                a[0]--;
                ok=1;
                    if(sum==S) afis();
            }
        }
            if(sum==S) afis();
            continue;
             
        if(sum==S) afis();
    }
     
     
    afis();
}
 
     
 
 
 
int main()
{
    time_t s;
    time(&s);
    srand(s%666013);
    freopen("semne.in", "r",stdin);
    scanf("%d %lld\n", &n, &S);
    for(int i=1;i<=n;i++) scanf("%d ", x+i);
    solve();
}