Cod sursa(job #1652409)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 14 martie 2016 22:38:23
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;

ifstream in("semne.in");
ofstream out("semne.out");

struct nr
{
    int val,poz;
};

const int N = 50005;

char ans[N+1];
nr v_adun[N];
nr v_scad[N];
int n,m;
long long s,s_crt;

int rand_interv(int a, int b) /// Random din intervalul [a, b]
{
    int dist;

    dist = b-a+1;
    return a + ((int)(rand()*2) % dist);
}

void afis()
{
    int i;

    for(i=1; i<=n; ++i) cout<<v_adun[i].val<<" "; cout<<"\n";
    for(i=1; i<=m; ++i) cout<<v_scad[i].val<<" "; cout<<"\n";
    cout<<"\n";
}

int main()
{
    srand(0);

    int i,index;

    in>>n>>s;

    for(i=1; i<=n; ++i)
    {
        in>>v_adun[i].val;
        v_adun[i].poz = i;
    }

    s_crt = 0;
    for(i=1; i<=n; ++i) s_crt += v_adun[i].val;

    cout<<s_crt;

    ///afis();
    while(s_crt != s)
    {
        ///cout<<"s_crt = "<<s_crt<<"\n";
        if(s_crt > s)
        {
            index = rand_interv(1, n); /// Aleg un oricare element pozitiv
            swap(v_adun[index], v_adun[n]); /// Il permut pe ultima pozitie

            s_crt -= v_adun[n].val * 2; /// Actualizez suma

            ++m;
            swap(v_scad[m], v_adun[n]); /// Mut elementul ales in celalalt vector
            v_scad[m].val *= -1; /// Semnul sau se schimba
            --n;
        }
        else // s_crt < s
        {
            /// Analog
            index = rand_interv(1, m);
            swap(v_scad[index], v_scad[m]);

            s_crt -= v_scad[m].val * 2;

            ++n;
            swap(v_adun[n], v_scad[m]);
            v_adun[n].val *= -1;
            --m;
        }
        ///afis();
    }

    for(i=1; i<=n; ++i) ans[v_adun[i].poz] = '+';
    for(i=1; i<=m; ++i) ans[v_scad[i].poz] = '-';
    ans[n+m+1] = 0;

    out<<(ans+1);
    //for(i=1; i<=n+m; ++i) out<<ans[i];

    //out<<"\n50000 0\n";
    //for(i=1; i<=50000; ++i) out<<i<<" ";


    return 0;
}