codeforce 1600
COFO::1582D Vupsen, Pupsen and 0
cofo problem
COFO::1582D Vupsen, Pupsen and 0
Problem
- level : 1600
- tag : constructive algorithms, math
- TIME
- to understand : 5
- to algorithm : 25
- to code : 15
- to debug : 5
- understanding edit : 5
Point
- 원소 중 0이 없는 배열 a가 주어집니다.
- 다음을 만족하는 배열 b를 구합니다.
- sum(a[i] * b[i]) = 0
- b[i] != 0
Design
- 최소공배수를 이용하여 풀이했습니다.
- 숫자가 넉넉히 크고, 2개씩 짝지어서 각 수의 최소공배수를 구하고
- 한쪽에는 +1 다른 한쪽에는 -1이 되도록 b를 구해주면 됩니다.
- 단, n이 홀수인 경우도 있기 때문에, 따로 핸들해줘야했습니다.
- edit의 방법도 알아둬야겠습니다.
- 매우 간단한 방법인데 GCD가 먼저 생각났네요
- a에 있는 원소를 순서만 바꿔서 출력하는 방법입니다.
- 예를 들어 a1 a2 가 있을때, ( 둘다 양수 )
- b1 = a2 b2 = a1 * -1 과 같은 방법으로 2개씩 쌍을 맞추면 됩니다.
- edit 또한, n이 홀수인 경우에 3개를 묶어서 처리했고 방법은 다음과 같습니다.
- a[i], a[j], a[k]가 주어졌다고 해봅시다.
- b[i] = a[j], b[j] = - (a[i] + a[k]), b[k] = a[j]
- 위처럼 하면 3개의 수의 합성곱의 값을 0으로 만들 수 있습니다.
Complexity
- O(NlogN)
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;
}