Cod sursa(job #1709)

Utilizator flo_demonBunau Florin flo_demon Data 14 decembrie 2006 16:21:22
Problema Semne Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <map>
#include <cmath>

using namespace std;

#define MAX 50006

int a[MAX];
int R, n, s, sum, saux;
map<int, int> semn_minus, semn_plus;
map<int, int>::iterator it, start, end;
int countt;
int semnn, LIM;

void Write();
void ReSeed();

int main()
{
    srand ( time(NULL) );
    FILE *fin = fopen("semne.in", "r");
    fscanf(fin, "%d%d", &n, &s);
    for (int i = 1; i <= n; ++i)
        fscanf(fin, "%d", &a[i]);
    fclose(fin);
    
  //  LIM = 3*(int)log((float)n);
    LIM = 33;
    
    ReSeed();
    
    int aux;
    while (1)
    {
        if (sum == s) { Write(); break; }
        if (countt >= LIM) ReSeed();
        else
        {
            countt++;
            saux = sum - s;
            if (saux > 0)
            {
                saux /= 2;
                it = semn_plus.find(saux);
                if (it == semn_plus.end())
                {
                    it = semn_plus.upper_bound(saux); 
                    if ((*it).second <= 0)
                    {
                        while (it != semn_plus.end() && (*it).second <= 0)
                            it++;
                        if (it == semn_plus.end())
                            while ((*it).second <= 0)
                                it--;
                    }
                }
                aux = (*it).first;
                sum -= 2*aux;
                semn_plus[aux]--;
                semn_minus[aux]++;
            }
            else
            {
                if (saux < 0)
                {
                    saux *= -1;
                    saux /= 2;
                    it = semn_minus.find(saux);
                    if (it == semn_minus.end())
                    {
                        it = semn_minus.upper_bound(saux);
                        if ((*it).second <= 0)
                        {
                            while (it != semn_minus.end() && (*it).second <= 0)
                                it++;
                            if (it == semn_plus.end())
                                while ((*it).second <= 0)
                                    it--;
                        }
                    }
                    aux = (*it).first;
                    sum += 2*aux;
                    semn_minus[aux]--;
                    semn_plus[aux]++;
                }
            }
        }
    }
    
    return 0;
}

void Write()
{
    FILE *fout = fopen("semne.out", "w");
    for (int i = 1; i <= n; ++i)
    {
        if (semn_minus[a[i]] > 0)
        {
            fprintf(fout, "-");
            semn_minus[a[i]]--;
        }
        else
        {
            if (semn_plus[a[i]] > 0)
            {
                fprintf(fout, "+");
                semn_plus[a[i]]--;
            }
        }
    }
    fclose(fout);
}

void ReSeed()
{
    semn_minus.clear();
    semn_plus.clear();
    sum = 0;
    countt = 0;
    for (int i = 1; i <= n; ++i)
    {
        R = rand()%2;
        if (R == 0)
        {
            if (semn_minus.count(a[i]) == 0)
                semn_minus[a[i]] = 1;
            else
                semn_minus[a[i]]++;
            semnn = -1;
        }
        if (R == 1)
        {
            if (semn_plus.count(a[i]) == 0)
                semn_plus[a[i]] = 1;
            else
                semn_plus[a[i]]++;
            semnn = 1;
        }
        sum += a[i] * semnn;
    }
}