Cod sursa(job #1927586)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 15 martie 2017 11:51:58
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 0.97 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("semne.in");
ofstream g("semne.out");
char sol[1<<16];
long long sum,S;
int n,p,m,t,i,a[1<<16],Plus[1<<16],Minus[1<<16];
int main()
{
    f>>n>>S;
    srand(time(0));
    for(i=1;i<=n;i++)
    {
        f>>a[i];
        t=rand()%2;
        if(t)
        {
            Plus[++p]=i;
            sum+=a[i];
            sol[i]='+';
        }
        else
        {
            Minus[++m]=i;
            sum-=a[i];
            sol[i]='-';
        }
    }
    while(sum!=S)
    {
        if(sum<S)
        {
            t=rand()%m+1;
            Plus[++p]=Minus[t];
            Minus[t]=Minus[m--];
            sol[Plus[p]]='+';
            sum+=2*a[Plus[p]];
        }
        else
        {
            t=rand()%p+1;
            Minus[++m]=Plus[t];
            Plus[t]=Plus[p--];
            sol[Minus[m]]='-';
            sum-=2*a[Minus[m]];
        }
    }
    g<<(sol+1);
    return 0;
}