Pagini recente » Cod sursa (job #1705132) | Cod sursa (job #3273778) | Cod sursa (job #1104399) | Cod sursa (job #89125) | Cod sursa (job #565507)
Cod sursa(job #565507)
#include <iostream>
#include <fstream>
#include <bitset>
#include <cstdlib>
#include <vector>
using namespace std;
#define MAXN 50005
typedef long long int64;
int v[MAXN];
bitset<MAXN> semn;
vector<int> p, m;
fstream fin ("semne.in", ios::in);
fstream fout ("semne.out", ios::out);
typedef vector<int>::iterator iter;
int main ()
{
int64 s, sum = 0, n;
fin >> n >> s;
srand (time (NULL));
for (int i = 0, x; i < n; ++i) {
fin >> v[i];
if (sum + v[i] <= s) {
p.push_back (i);
sum += v[i];
semn[i] = true;
} else {
m.push_back (i);
sum -= v[i];
semn[i] = false;
}
}
while (sum != s) {
if (sum > s) {
int i = rand () % p.size ();
sum -= 2 * v[p[i]];
semn[p[i]] = false;
m.push_back (p[i]);
p[i] = p[p.size () - 1];
p.pop_back ();
} else {
int i = rand () % m.size ();
sum += 2 * v[m[i]];
semn[m[i]] = true;
p.push_back (m[i]);
m[i] = m[m.size () - 1];
m.pop_back ();
}
}
for (int i = 1; i <= n; ++i) {
fout << (semn[i] ? '+' : '-');
}
fout << endl;
fin.close ();
fout.close ();
return 0;
}