Cod sursa(job #3343160)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 26 februarie 2026 16:08:04
Problema Semne Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 50000;
int v[MAXN], v1[MAXN], v2[MAXN];
char f[MAXN];
int main()
{
    //s1 + s2 = suma numerelor
    //s1 - s2 = s
    //deci 2 * s1 = suma numerelor + s
    //aleg un subset sa aiba suma s1 si daca s1 > sum + s atunci scot un numar random altfel daca e mai mic adaug un numar random
    FILE *fin, *fout;
    int n, nr1, nr2, i, p;
    long long sum, s, s1;
    fin = fopen("semne.in", "r");
    fscanf(fin, "%d%lld", &n, &s);
    sum = s;
    nr1 = nr2 = s1 = 0;
    for (i = 0; i < n; i++) {
        fscanf(fin, "%d", &v[i]);
        sum += v[i];
        v2[nr2] = i;
        nr2++;
    }
    fclose(fin);
    while (2 * s1 != sum) {
        if (2 * s1 < sum) {
            p = rng() % nr2;
            v1[nr1] = v2[p];
            nr1++;
            s1 += v[v2[p]];
            //il elimin din al doilea vector
            v2[p] = v2[nr2 - 1];
            nr2--;
        } else {
            p = rng() % nr1;
            v2[nr2] = v1[p];
            nr2++;
            s1 -= v[v1[p]];
            //il elimin din primul vector
            v1[p] = v1[nr1 - 1];
            nr1--;
        }
    }
    for (i = 0; i < nr1; i++) {
        f[v1[i]] = 1;
    }
    fout = fopen("semne.out", "w");
    for (i = 0; i < n; i++) {
        if (f[i] == 0) {
            fputc('-', fout);
        } else {
            fputc('+', fout);
        }
    }
    fputc('\n', fout);
    fclose(fout);
    return 0;
}