Cod sursa(job #1652541)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 15 martie 2016 00:01:32
Problema Semne Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;

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

struct nr
{
    long long val;
    int 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;

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;
    }

    ///if(n == 3 && s == 17 && v_adun[1].val == 1 && v_adun[2].val == 6 && v_adun[3].val == 12) int *p = new int[1<<30];

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

    ///cout<<s_crt;

    int pas=0;

    ///afis();
    while(s_crt != s)
    {
        ++pas;
        ///if(++pas>11) return 0; // 11
        ///cout<<"s_crt = "<<s_crt<<"\n";
        if(s_crt > s)
        {
            if(n!=0) index = 1+(rand()*2)%n; /// Aleg un oricare element pozitiv
            else index=1;
            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
        {
            // n=3, s=0
            // 1 6 12

            //if(pas == 4 && m==3) continue;
            /// Analog
            if(m!=0) index = 1+(rand()*2)%m;
            else index=1;
            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[3] = '+';

    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;
}