【24.17%】【codeforces 721D】Maxim and Array

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array ai either with ai + x or with ai - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. ) can reach, if Maxim would apply no more than k operations to it. Please help him in that.

Input
The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers a1, a2, …, an () — the elements of the array found by Maxim.

Output
Print n integers b1, b2, …, bn in the only line — the array elements after applying no more than k operations to the array. In particular, should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.

Examples
input
5 3 1
5 4 3 5 2
output
5 4 3 5 -1
input
5 3 1
5 4 3 5 5
output
5 4 0 5 5
input
5 3 1
5 4 4 5 5
output
5 1 4 5 5
input
3 2 7
5 4 2
output
5 11 -5

【题目链接】:http://codeforces.com/contest/721/problem/D

【题解】

如果负数的个数为偶数个.
则需要把某一个数的符号变一下.让负数的个数变成奇数个.
(负数肯定比正数大!);
显然。我们让那个绝对值最小的数变号是最好的.
之后如果还有剩余的操作次数
就尽量让所有的数都”平均一点”;
这样最后连乘的结果最大.(是负数所以结果反而更小);
方法就是让绝对值最小的数的绝对值变大.
(每次都操作绝对值最小的数，让它的绝对值变大);
(绝对值最小的数可以用一个set维护出来);
那个重载<不包括==,所以如果想等就要随便想一个东西写上去.
(如果想到就直接返回true这样写最好)
不然会有东西莫名其妙地消失。

【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

const int MAXN = 2e5+10;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);

LL a[MAXN];

struct node
{
    int x,sign;
    friend bool operator < (node aa,node bb)
    {
        if (abs(a[aa.x]) != abs(a[bb.x]))
            return abs(a[aa.x]) < abs(a[bb.x]);
        else
            return true;
    }

};

int n,k,fu=0;
LL x;
set <node> dic;

int main()
{
    //freopen("F:\\rush.txt","r",stdin);
    rei(n);rei(k);rel(x);
    rep1(i,1,n)
    {
        rel(a[i]);
        node temp;
        if (a[i] < 0)
            temp.sign = -1,fu++;
        else
            temp.sign = 1;
        temp.x = i;
        dic.insert(temp);
    }
    if (!(fu&1))
    {
        while (k)
        {
            k--;
            int po = dic.begin()->x;
            int s = dic.begin()->sign;
            dic.erase(dic.begin());
            node temp1;
            LL temp = abs(a[po]);
            if (temp < x)
            {
                s*=-1;
                temp-=x;
                a[po] = abs(temp)*s;
                temp1.sign = s;temp1.x = po;
                dic.insert(temp1);
                break;
            }
            else
            {
                temp-=x;
                a[po] = temp*s;
                temp1.sign = s;temp1.x = po;
                dic.insert(temp1);
            }
        }
    }
    while (k)
    {
        k--;
        int po = dic.begin()->x;
        int s = dic.begin()->sign;
        dic.erase(dic.begin());
        node temp1;
        LL temp = abs(a[po]);
        temp += x;
        temp*=s;
        a[po] = temp;
        temp1.sign = s;
        temp1.x = po;
        dic.insert(temp1);
    }
    rep1(i,1,n)
        {
            printf("%I64d",a[i]);
            if (i==n)
                puts("");
            else
                putchar(' ');
        }
    return 0;
}