2 seconds
256 megabytes
standard input
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.
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.
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.
5 3 1
5 4 3 5 2
5 4 3 5 -1
5 3 1
5 4 3 5 5
5 4 0 5 5
5 3 1
5 4 4 5 5
5 1 4 5 5
3 2 7
5 4 2
5 11 -5
题意：n个数，可以修改k次，每次可以+x或者-x，使得成绩最小；
思路：每次寻找绝对值最小的那个数，判断负数的个数，进行+x或者-x；
ps：优先队列也可做；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
const int N=2e5+,M=4e6+,inf=1e9+,mod=1e9+;
const ll INF=1e18+;
struct is
{
ll num;
int pos;
}tree[N<<];
ll ans[N];
void pushup(int pos)
{
tree[pos].num=min(tree[pos<<].num,tree[pos<<|].num);
}
void buildtree(int l,int r,int pos)
{
if(l==r)
{
tree[pos].num=abs(ans[l]);
tree[pos].pos=l;
return;
}
int mid=(l+r)>>;
buildtree(l,mid,pos<<);
buildtree(mid+,r,pos<<|);
pushup(pos);
}
void update(int p,ll c,int l,int r,int pos)
{
if(p==r&&p==l)
{
tree[pos].num=abs(c);
return;
}
int mid=(l+r)>>;
if(p<=mid)
update(p,c,l,mid,pos<<);
else
update(p,c,mid+,r,pos<<|);
pushup(pos);
}
int query(ll x,int l,int r,int pos)
{
if(l==r&&tree[pos].num==x)
return tree[pos].pos;
int mid=(l+r)>>;
if(tree[pos<<].num==x)
return query(x,l,mid,pos<<);
else
return query(x,mid+,r,pos<<|);
}
int main()
{
int n,m,k;
int flag=;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)
{
scanf("%lld",&ans[i]);
if(ans[i]<)flag++;
}
buildtree(,n,);
while(m--)
{
ll x=tree[].num;
int pos=query(x,,n,);
if(flag&)
{
if(ans[pos]>=)
ans[pos]+=k;
else
ans[pos]-=k;
update(pos,ans[pos],,n,);
}
else
{
if(ans[pos]>=)
{
ans[pos]=ans[pos]-k;
if(ans[pos]<)
flag++;
}
else
{
ans[pos]=ans[pos]+k;
if(ans[pos]>=)
flag--;
}
update(pos,ans[pos],,n,);
}
}
for(int i=;i<=n;i++)
printf("%lld ",ans[i]);
return ;
}