Cod sursa(job #1201055)

Utilizator misinozzz zzz misino Data 24 iunie 2014 13:35:31
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.06 kb
#include<fstream>
#include<algorithm>
#include<ctime>
#define N 50001
using namespace std;
ifstream f("semne.in");
ofstream g("semne.out");
int i,n,l1,l2,x;
long long v1[N],v2[N],v[N];
bool p[N];
long long s,suma;
int main()
{
    f>>n>>s;
    srand(time(NULL));

    for(i=0;i<n;++i)
    {
        f>>v[i];
        x=rand()%2;
        p[i]=x;
        if(x)
        {
            suma-=v[i];
            v1[l1++]=i;
        }
        else
        {
            suma+=v[i];
            v2[l2++]=i;
        }
    }
    while(suma!=s)
    {
        if(suma>s)
        {
            x=rand()%l2;
            suma-=(2*v[v2[x]]);
            v1[l1++]=v2[x];
            --l2;
            p[v2[x]]^=1;
            v2[x]=v2[l2];

        }
        else
        {
            x=rand()%l1;
            suma+=(2*v[v1[x]]);
            v2[l2++]=v1[x];
            p[v1[x]]^=1;
            --l1;
            v1[x]=v1[l1];
        }
    }
    for(i=0;i<n;++i)
    if(p[i])
    g<<'-';
    else
    g<<'+';
    g<<'\n';
    return  0;
}