COFO::1582D Vupsen, Pupsen and 0

Problem

Point

Design

Complexity

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

int n;
vector<pair<ll,int> > a, b;
ll gcd(ll x, ll y){return y == 0 ? x : gcd(y, x%y);}
ll lcm(ll x, ll y){ return x * y / gcd(x, y);}
void solve() {
    cin >> n;
    a.clear(); b.clear();
    a = vector<pair<ll,int> > (n);
    b = vector<pair<ll,int> > (n);
    rep(i, 0, n) {
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(all(a));
    auto makePlus = [](ll x){return x < 0 ? x : x;};
    int st = 0;
    if (n %2) {
        ll k = lcm(a[0].fi, lcm(a[1].fi, a[2].fi));
        b[0].fi = makePlus( k / a[0].fi );      b[0].se = a[0].se;
        b[1].fi = makePlus( k / a[1].fi );      b[1].se = a[1].se;
        b[2].fi = makePlus( k / a[2].fi )* -2;  b[2].se = a[2].se;
        st = 3;
    }
    for(st; st < n; st += 2) {
        ll k = lcm(a[st].fi, a[st + 1].fi);
        b[st].fi = makePlus(k / a[st].fi);                b[st].se = a[st].se;
        b[st + 1].fi = makePlus(k / a[st + 1].fi) * -1 ;  b[st + 1].se = a[st + 1].se;
    }

    auto cmp = [](pair<ll, int> x, pair<ll, int> y) {
        return x.se < y.se;
    };
    sort(all(b), cmp);
    rep(i, 0, n) cout << b[i].fi << " ";
    cout << '\n';
}
int main(){
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}