Codeforces #176 Div2 C "Lucky Permutation"
問題
http://codeforces.com/contest/287/problem/C
訳
サイズnのpermutation pとは整数のシーケンスp(1), p(2), p(3)... p(n)であり、
このシーケンス内に同じ数値が2つとなく、数値は1~Nのようなものをいう。
lucky permutation pとはp(p(i)) = n - i + 1となっている
permutationの事である。
整数Nが与えられるので、サイズがNのlucky permutation p を表示せよ。
そのサイズでlucky permutationが作れなければ-1を表示せよ。
制約
1 <= N <= 10^5
考えた事
なんじゃこりゃ・・全然分からんぞ・・・
Nが4 5の時は出来るのに、なんで6 7の時は出来ないんだ?
あれ、なんか必ず4回で一巡するな
しかも対称的になってる!
ってことはNが4の倍数ならlucky permutation作れそう。
Nが奇数の場合真ん中はindexと値を同じにすればいいね。
というか同じにしなきゃダメだね。
だからNかN-1が4の倍数であればlucky permutationを作れる。
あとは頑張って実装
ソースコード
int main() { int n; cin >> n; // lucky permutationが作れない if( n % 4 != 0 && (n - 1) % 4 != 0 ){ cout << -1 << endl; return 0; } bool odd = (n % 2 == 0); for( int i = 1; i <= n; i++ ){ int p; // index i に入れる値 // 前半 if( i <= n / 2 ){ if( i % 2 != 0 ){ p = i + 1; }else{ p = n - (i / 2 - 1) * 2; } } // 奇数でちょうど真ん中 else if( !odd && i == n / 2 + 1 ){ p = i; } // 後半で偶数 else if( odd ){ if( i % 2 != 0 ){ p = n - i; }else{ p = i - 1; } } // 後半で奇数 else{ if( i % 2 != 0 ){ p = i - 1; }else{ p = n - i; } } printf( "%d ", p ); } }