[Codeforces/코드포스] Codeforces Round #813 (Div. 2) B - Woeful Permutation

Problem - 1712B - Codeforces

---

 

유클리드 호제법이 아닌 패턴찾기

---

---

• 제목

Woeful Permutation

---

• 조건

time limit per test : 1 second

memory limit per test : 256 megabytes

input : standard input

output : standard output

---

• 문제

You are given a positive integer n.

Find any permutation p of length n such that the sum lcm(1,p1)+lcm(2,p2)+…+lcm(n,pn) is as large as possible.

Here lcm(x,y) denotes the least common multiple (LCM) of integers x and y.

A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

---

• 입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000). Description of the test cases follows.

The only line for each test case contains a single integer n (1≤n≤105).

It is guaranteed that the sum of n over all test cases does not exceed 105.

---

• 출력

For each test case print n integers p1, p2, …, pn — the permutation with the maximum possible value of lcm(1,p1)+lcm(2,p2)+…+lcm(n,pn).

If there are multiple answers, print any of them.

---

예제 입력1	예제 출력1
2 1 2	1 2 1

---

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define endl '\n'
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc, sz;
    cin >> tc;
    while(tc--){
    	cin >> sz;
    	if(sz % 2 == 0){
    		for(int n = 1 ; n <= sz ; n++){
    			if(n % 2 == 0) cout << n - 1 << ' ';
    			if(n % 2 == 1) cout << n + 1 << ' ';
			}
		}
		else{
			cout << 1 << ' ';
    		for(int n = 2 ; n <= sz ; n++){
    			if(n % 2 == 0) cout << n + 1 << ' ';
    			if(n % 2 == 1) cout << n - 1 << ' ';
			}
		}
		cout << endl;
	}
    return 0;
}