# C. Isamatdin and His Magic Wand! [문제 링크](https://codeforces.com/contest/2167/problem/C) ## Problem Statement Isamatdin has $n$ toys arranged in a row. The $i$-th toy has an integer $a_i$. He wanted to sort them because otherwise, his mother would scold him. However, Isamatdin never liked arranging toys in order, so his friend JahonaliX gave him a magic wand to help. Unfortunately, JahonaliX made a small mistake while creating the wand. But Isamatdin couldn't wait any longer and decided to use the broken wand anyway. The wand can only swap two toys if their integers have **different parity** (one is even, the other is odd). In other words, you can swap toys in positions $(i, j)$ only if $a_i \bmod 2 \ne a_j \bmod 2$, where $\bmod$ — is the remainder of integer division. Now he wants to know the **lexicographically smallest** arrangement he can achieve using this broken wand. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of toys. The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the integers of the toys. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output $n$ integers — the lexicographically smallest sequence that can be obtained using the described operation. ## Footnote A sequence $p$ is *lexicographically smaller* than a sequence $q$ if there exists an index $i$ such that $p_j = q_j$ for all $j < i$, and $p_i < q_i$. ## 풀이 홀수와 짝수가 둘 다 등장하면, 수들이 어디로든 이동할 수 있기에 정렬하여 출력하고, 그렇지 않으면 그냥 출력하면 됩니다. ``` c++ #include<bits/stdc++.h> using namespace std; int a[200000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; bool even=false, odd=false; for(int i=0;i<n;i++) { cin >> a[i]; if(a[i]%2) odd=true; else even=true; } if(odd && even) sort(a, a+n); for(int i=0;i<n;i++) cout << a[i] << ' '; cout << '\n'; } } ```