Pagini recente » Cod sursa (job #1460205) | Cod sursa (job #3303892) | Cod sursa (job #3321625) | Cod sursa (job #3326228) | Cod sursa (job #3343160)
#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;
}