Cod sursa(job #2108103)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 17 ianuarie 2018 21:42:23
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
#define MAXN 50000

long long v[1 + MAXN];
int f[1 + MAXN];
std::vector <int> P, Q;
int main(){
    FILE*fi,*fo;
    fi = fopen("semne.in","r");
    fo = fopen("semne.out","w");

    int N;
    long long s;
    fscanf(fi,"%d%lld", &N, &s);
    for(int i = 1; i <= N; i++)
        fscanf(fi,"%lld", &v[i]);
    std::sort(v + 1, v + N + 1);
    long long sum = 0;
    int p = 0, n = 0;
    for(int i = 1; i <= N; i++){
        if(sum <= s){
            f[i] = 1;
            P.push_back(i);
            p++;
            sum += v[i];
        }
        else{
            f[i] = -1;
            Q.push_back(i);
            n++;
            sum -= v[i];
        }
    }

    while(sum != s){
        int i, j = 1, con = 0;
        if(sum > s){
            i = rand() % p;
            p--;
            n++;
            j = P[i];
            P[i] = P[P.size() - 1];
            P.pop_back();
            Q.push_back(j);
        }
        else{
            i = rand() % n;
            p++;
            n--;
            j = Q[i];
            Q[i] = Q[Q.size() - 1];
            Q.pop_back();
            P.push_back(j);
        }
        sum -= f[j] * v[j];
        f[j] = -f[j];
        sum += f[j] * v[j];
    }
    for(int i = 1; i <= N; i++)
        if(f[i] == 1) fprintf(fo,"+");
        else fprintf(fo,"-");

    return 0;
}