Cod sursa(job #1251095)

Utilizator sebinechitasebi nechita sebinechita Data 28 octombrie 2014 22:15:59
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("semne.in");
ofstream fout("semne.out");
#define MAX 50002
//#define cout fout
int a[MAX], b[MAX], viz[MAX], v[MAX];

int main()
{
    int n, i, c, x=0, y=0;
    long long S, s=0;
    fin>>n>>S;
    srand(time(0));
    for(i=1;i<=n;i++)
    {
        fin>>c;
        v[i]=c;
        if(rand()%2)
        {
            a[++x]=i;
            s+=c;
        }
        else
        {
            b[++y]=i;
            s-=c;
        }
    }
    while(s!=S)
    {
        if(s<S)
        {
            i=rand()%y+1;
            swap(b[i], b[y]);
            a[++x]=b[y];
            s+=2*v[b[y]];
            y--;
        }
        else
        {
            i=rand()%x+1;
            swap(a[i], a[x]);
            b[++y]=a[x];
            s-=2*v[a[x]];
            x--;
        }
    }
    for(i=1;i<=x;i++)
        viz[a[i]]=1;
    for(i=1;i<=n;i++)
    {
        if(viz[i])
            cout << "+";
        else
            cout << "-";
    }

}