Cod sursa(job #2595329)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 7 aprilie 2020 15:50:31
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;
int v[50010] , sol[50010];
vector <int> pls , mis;
map <long long,int> mp[2];
int main()
{
    FILE *fin = fopen ("semne.in","r");
    FILE *fout = fopen ("semne.out","w");
    int n , i , pos , nr , change = -1;
    long long s , sum=0 , dif;
    srand(time(0));
    fscanf (fin,"%d",&n);
    fscanf (fin,"%lld",&s);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        sum += v[i];
        pls.push_back(i);
        sol[i] = 1;
        mp[1][v[i]]++;
    }
    while (sum != s){

        if (sum > s){ /// scot din plus bag in minus

            dif = sum - s;
            if (dif % 2 == 0){
                dif /= 2;
                if (mp[1][dif]){
                    change = dif;
                    break;
                }
            }



            pos = 1LL * rand() * rand() % pls.size();
            nr = pls[pos];
            sol[nr] = -sol[nr];
            pls.erase(pls.begin() + pos);
            mis.push_back(nr);
            mp[0][v[nr]]++;
            mp[1][v[nr]]--;
            sum -= 2 * v[nr];
        }
        else {

            dif = s - sum;
            if (dif % 2 == 0){
                dif /= 2;
                if (mp[0][dif]){
                    change = dif;
                    break;
                }
            }

            pos = 1LL * rand() * rand() % mis.size();
            nr = mis[pos];
            sol[nr] = -sol[nr];
            mis.erase(mis.begin() + pos);
            pls.push_back(nr);
            mp[1][v[nr]]++;
            mp[0][v[nr]]--;
            sum += 2 * v[nr];
        }

    }
    for (i = 1 ; i <= n ; i++){

        if (v[i] == change){
            if (s > sum && sol[i] == -1)
                sol[i] = 1 , change = -1;
            else if (s < sum && sol[i] == 1)
                sol[i] = -1 , change = -1;
        }

        if (sol[i] == 1)
            fprintf (fout,"+");
        else fprintf (fout,"-");
    }
    return 0;
}