WARush

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

Codeforces #183 Div2 C "Lucky Permutation Triple"

問題

http://codeforces.com/contest/304/problem/C

バイクは順列に興味がある。長さnの順列とは0~n-1までの整数がそれぞれちょうど1回だけ含まれる整数の配列である。例えば、[ 0, 2, 1 ]は長さ3の順列であるが、[ 0, 2, 2 ]や[ 1, 2, 3 ]はそうではない。

長さnの3つの順列(a, b, c)は下記のようなとき"Lucky Permutation Triple"と呼ばれる。
f:id:Ekaing:20130602093919p:plain
a_iは順列 a の i 番目の要素を表す。そして全体では、任意の 0 <= i <= n で a_i + b_i mod n と c_i mod nは等しく、重複が無いことを意味する。

nが与えられるので"Lucky Permuation Triple"を見つけ、それを出力せよ。

制約

1 <= n <= 10^5


考えた事

nは偶数なら"lucky Permutation Triple"はできない。え?証明・・・?

紙にいっぱい書いて試した(証明終)

nが奇数、たとえば9なら順列aは0, 1, 2, 3, 4, 5, 6, 7, 8 とまず順番に置いてしまう。
順列bは後ろから1, 3, 5, 7, 0, 2, 4, 6, 8と 1 から初めて2ずつ増やしていけば、順列cは8, 7, 6, 5, 4, 3, 2, 1, 0と重複無くできる。

a - 0 1 2 3 4 5 6 7 8
b - 8 6 4 2 0 7 5 3 1
c - 8 7 6 5 4 3 2 1 0

ソースコード

int main() {
    int n;
    cin >> n;

    // 偶数はできない
    if( n % 2 == 0 ){
        cout << -1 << endl;
        return 0;
    }

    // a
    for( int i = 0; i < n; i++ ){
        printf( "%d%c", i, (i + 1 == n ? '\n' : ' ') );
    }

    // b
    for( int i = 0; i < n; i++ ){
        int m = n - i - 1;
        int j = m - i;
        if( j < 0 ) j += n;
        printf( "%d%c", j, (i + 1 == n ? '\n' : ' ') );
    }

    // c
    for( int i = 0; i < n; i++ ){
        int m = n - i - 1;
        printf( "%d%c", m, (i + 1 == n ? '\n' : ' ') );
    }
}