Cod sursa(job #960616)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 20:21:46
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.32 kb
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
long long n, s, ss, v[50050], semn[50050];
int i;
vector<int> m, p;
int main()
{
    freopen("semne.in" ,"r", stdin);
    freopen("semne.out", "w", stdout);
    srand(time(0));
    scanf("%lld%lld", &n, &s);
    for(i=1;i<=n;i++)
        scanf("%lld", &v[i]);
    for(i=1;i<=n;i++)
        if(rand()%2)
        {
            ss-=v[i];
            semn[i]=-1;
            m.push_back(i);
        }
        else
        {
            ss += v[i];
            semn[i] = 1;
            p.push_back(i);
        }
     
    while(ss != s)
        if(ss > s)
        {
            int ind = rand() % p.size();
            swap(p[ind], p[p.size() - 1]);
            m.push_back(p.back());
            ss -= 2 * v[p.back()];
            semn[p.back()] = -1;
            p.pop_back();
        }
        else
        {
            int ind = rand() % m.size();
            swap(m[ind], m[m.size() - 1]);
            p.push_back(m.back());
            ss += 2 * v[m.back()];
            semn[m.back()] = 1;
            m.pop_back();
        }
     
    for(i=1;i<=n;i++)
        if(semn[i] == 1)
            printf("+");
        else
            printf("-");
    return 0;
}