Codeforces Round #374 (Div. 2) D. Maxim and Array贪心+ 最小堆

D. Maxim and Array time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard 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

贪心，一开始的思路错了，一开始想先找出负数的个数，如果为偶数个则找到绝对值最小的那个将它变成异号，否则就不变。 然后再找到绝对值最小的那个，将剩余的k全部加或者减在上面，就是这个地方有了问题，就比如 3 2 3 -2 4 6 如果照着我的想法，就是 -8 4 6 但是 -5 7 6明显更好，所以我想到了应该k的变化应该一次次进行，每次找到绝对值最小的那个进行变化。 #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<cmath> #include<stack> const int inf=0x3f3f3f3f; typedef long long LL; using namespace std; const int MAXN=2e5+10; LL a[MAXN]; LL b[MAXN]; struct Node { int id; LL value; Node(int i,LL v) { id=i; value=v; } }; struct cmp { bool operator()(Node a,Node b){ return a.value>b.value; } }; int main() { int n,k,x; while(cin>>n>>k>>x) { int sum=0; for(int i=1;i<=n;i++) { scanf("%I64d",&a[i]); b[i]=a[i]; if(a[i]<0) { sum++; b[i]*=-1LL; } } int h=0; if(sum%2==0) { LL MIN=b[1]; int index=1; for(int i=2;i<=n;i++) { if(MIN>b[i]) { MIN=b[i]; index=i; } } int t=k; if(MIN/x+1<=k) { b[index]-=LL(MIN/x+1)*LL(x); k-=(MIN/x+1); } else { b[index]-=LL(k*x); k=0; } if(a[index]<0) { a[index]+=LL(t-k)*LL(x); } else { a[index]-=LL(t-k)*LL(x); } } if(k) { for(int i=1;i<=n;i++) { b[i]=a[i]; if(b[i]<0) { b[i]*=(-1LL); } } priority_queue<Node,vector<Node>,cmp> Q; for(int i=1;i<=n;i++) { Q.push(Node(i,b[i])); } while(k) { Node u=Q.top(); Q.pop(); b[u.id]+=LL(x); Q.push(Node(u.id,b[u.id])); k--; } for(int i=1;i<=n;i++) { if(a[i]<0) { a[i]=b[i]*-1LL; } else { a[i]=b[i]; } } } printf("%I64d",a[1]); for(int i=2;i<=n;i++) { printf(" %I64d",a[i]); } cout<<endl; } }