WARush

SRMの結果とか、解けた問題のコードを書いていきます

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回で一巡するな
f:id:Ekaing:20130324130902j:plain
f:id:Ekaing:20130324131850j:plain

しかも対称的になってる!
f:id:Ekaing:20130324165438j:plain
ってことはNが4の倍数ならlucky permutation作れそう。


Nが奇数の場合真ん中はindexと値を同じにすればいいね。
というか同じにしなきゃダメだね。
f:id:Ekaing:20130324131002j:plain

だから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 );        
    }
}