Cod sursa(job #1514563)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 31 octombrie 2015 12:33:42
Problema Semne Scor 95
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.23 kb
#include <bits/stdc++.h>
#define NMAX 50001

using namespace std;

ifstream in("semne.in");
ofstream out("semne.out");
int n;
long long int s,a[NMAX];
long long int x = 0;
int add[NMAX],low[NMAX];
int u = 0, p = 0;
bool a_sem[NMAX];

int main()
{
    in>>n>>s;
    for(int i=1;i<=n;i++)
    {
        in>>a[i];
        if(x<s)
        {
            add[++u] = i;
            x+=a[i];
        }
        else
        {
            low[++p] = i;
            x-=a[i];
        }
    }
    in.close();
    int b;
    while(x!=s)
    {
        if((x<s) && (p>0))
        {
            b = rand()%p+1;
            x+=2*a[low[b]];
            add[++u] = low[b];
            low[b] = low[p];
            p--;
        }
        else
            if(u>0)
        {
            b = rand()%u+1;
            x-=2*a[add[b]];
            low[++p] = add[b];
            add[b] = add[u];
            u--;
        }
    }
    for(int i=1;i<=max(p,u);i++)
    {
        if(i<=u)
            a_sem[add[i]] = 1;
        if(i<=p)
            a_sem[low[i]] = 0;
    }
    for(int i=1;i<=n;i++)
        if(a_sem[i] == 1)
        out<<"+";
    else
        out<<"-";
    out<<'\n';
    out.close();
    return 0;
}