Pagini recente » Cod sursa (job #2752499) | Cod sursa (job #2360568) | Cod sursa (job #1534070) | Cod sursa (job #1838979) | Cod sursa (job #2595329)
#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;
}