Cod sursa(job #404749)

Utilizator mihai995mihai995 mihai995 Data 26 februarie 2010 17:23:15
Problema Semne Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std; 
int poz[500010],neg[500010],v[500010];
bool semn[50010];
 
int main()
{
    int n,i;
    long long s=0,sum=0; 
    ifstream f("semne.in");
    ofstream o("semne.out");	
    f>>n>>s;
    for (i=1;i<=n;i++)
    {
        f>>v[i];
        if (sum<s)
        {
            sum+=v[i];
            poz[poz[0]++]=i;
            semn[i]=true;
        } 
        else
        {
            sum-=v[i];
            neg[neg[0]++]=i;
        }
    } 
    srand(time(NULL));
    while (sum!=s) 
        if (sum<s) 
        {
            int r=rand()%neg[0]+1;
            semn[neg[r]]=true;
            sum+=2*v[neg[r]];
            poz[poz[0]++]=neg[r];
            neg[r]=neg[neg[0]];
            neg[0]--;
        }
        else 
        {
            int r=rand()%poz[0]+1 ;
            semn[poz[r]]=false;
            sum-=2*v[poz[r]];
            neg[neg[0]++]=poz[r];
            poz[r]=poz[poz[0]];
            poz[0]--;
        }
    for (i=1;i<=n;i++) 
        if (semn[i]) o<<"+";        
           else o<<"-";     
    return 0;
}