Cod sursa(job #2060281)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 8 noiembrie 2017 01:26:11
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.21 kb
#include <bits/stdc++.h>

#define MaxN 50005
#define MOD 666013
#define INF 2140000000

using namespace std;

FILE *IN,*OUT;

long long S=0,Q;
int v[MaxN],N;
bool sign[MaxN];
vector<int>p,m;
int main()
{
    IN=fopen("semne.in","r");
    OUT=fopen("semne.out","w");

    srand(time(NULL));

    fscanf(IN,"%d%lld",&N,&Q);

    for(int i=1;i<=N;i++)
        fscanf(IN,"%d",&v[i]);

    for(int i=1;i<=N;i++)
    {
        if(S>Q)
            S-=v[i],m.push_back(i);
        else S+=v[i],sign[i]=1,p.push_back(i);
    }
    int pos;
    while(S!=Q)
    {
        if(S>Q)
        {
            pos=rand()%p.size();
            m.push_back(p[pos]);
            swap(p[pos],p[p.size()-1]);
            pos=p[p.size()-1];
            p.pop_back();
        }
        if(S<Q)
        {
            pos=rand()%m.size();
            p.push_back(m[pos]);
            swap(m[pos],m[m.size()-1]);
            pos=m[m.size()-1];
            m.pop_back();
        }
        if(sign[pos])
            S-=v[pos]<<1;
        else S+=v[pos]<<1;
        sign[pos]^=1;
    }

    for(int i=1;i<=N;i++)
    {
        if(sign[i])fprintf(OUT,"+");
        else fprintf(OUT,"-");
    }
    return 0;
}