Cod sursa(job #984480)

Utilizator misinozzz zzz misino Data 14 august 2013 16:36:40
Problema Semne Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include<fstream>
#include<algorithm>
#include<ctime>
#include<cstdio>
#define N 50001
using namespace std;
ofstream g("semne.out");
int i,n,l1,l2,x;
long long v1[N],v2[N],v[N],p[N];
long long s,suma;
int D=999999,poz=D+1;
char buf[1000006];
inline long long ianr()
{
    long long nr=0;
    while(buf[poz]<'0'||buf[poz]>'9')
    if(++poz>=D)
    fread(buf,D,1,stdin),poz=0;
    while('0'<=buf[poz]&&buf[poz]<='9')
    {
        nr=nr*10+buf[poz]-'0';
        if(++poz>=D)
        fread(buf,D,1,stdout),poz=0;
    }
    return nr;
}

int main()
{
    freopen("semne.in","r",stdin);
    n=ianr();
    s=ianr();
//    f>>n>>s;
    srand(time(NULL));
    for(i=0;i<n;++i)
    {
        v[i]=ianr();
        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;
}