Cod sursa(job #1284364)

Utilizator aaron72Armand Ioan Anusca Popa aaron72 Data 6 decembrie 2014 14:31:17
Problema Semne Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

int a[50005],v1[50005],v2[50005],n,n1,n2;
long long s1,s2;

int main()
{
    int x,i,p,j;
    ifstream fin("semne.in");
    fin>>n>>x;
    for(i=1;i<=n;i++) fin>>a[i];
    fin.close();
    for(i=1;i<=n/2;i++)
    {
        v1[i]=i;
        s1+=a[i];
    }
    n1=n/2;
    n2=0;
    for(i=n/2+1;i<=n;i++)
    {
        v2[++n2]=i;
        s2+=a[i];
    }
    srand(time(0));
    while(s1-s2!=x)
    {
        if(s1-s2>x)
        {
            p=rand()%n1+1;
            s1-=a[v1[p]];
            s2+=a[v1[p]];
            v2[++n2]=v1[p];
            v1[p]=v1[n1--];
        }
        else
        {
            p=rand()%n2+1;
            s1+=a[v2[p]];
            s2-=a[v2[p]];
            v1[++n1]=v2[p];
            v2[p]=v2[n2--];
        }
    }
    ofstream fout("semne.out");
    sort(v1+1,v1+n1+1);
    sort(v2+1,v2+n2+1);
    i=1;j=1;
    v1[n1+1]=v2[n2+1]=1000000;
    for(p=1;p<=n;p++)
    {
        if(v1[i]<v2[j])
        {
            fout<<"+";
            i++;
        }
        else
        {
            fout<<"-";
            j++;
        }
    }
    fout<<"\n";
    fout.close();
    return 0;
}