WARush

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

Codeforces #177 Div2 E "Polo the Penguin and XOR operation"

問題

http://codeforces.com/contest/289/problem/E

0~Nの数値が含まれている順列について考える。

順列P = P(0), P(1),... P(N)の美しさを
( (0 xor P(1) ) + ( (1 xor P(1) ) + ... + ( (N xor P(N) )と定義する。

0からNの数値を1つずつ持つ順列のなかで、最も美しい順列の美しさの値と、
その内容を表示せよ。

制約

1 <= N <= 10^6


紙に書いたこと

うむ・・
f:id:Ekaing:20130404000559j:plain

うむうむ・・
f:id:Ekaing:20130404000619j:plain

おおう?
f:id:Ekaing:20130404000635j:plain


おおお!!
f:id:Ekaing:20130404000651j:plain


何か知らんが・・・
1を1つも失うことのない順列を必ず作れそうだ

解法

大きいインデックスから貪欲にベストな数値を見つけてけばOK!



ソースコード

int a[1000010]; // 美しすぎる順列

int main() {

    int N;
    cin >> N;

    // 美しさを1つも失うことない順列が必ず作れる
    long long ans = (long long)N * (N+1); 
    for( int i = N; i >= 0; ){
        // 111...111を作る
        int p = 1;
        int t = i;
        while( t ){
            t >>= 1;
            p <<= 1;
        }
        p -= 1; // 111...111
        int j = p ^ i; // iにとってベストなペア
        int nextI = j - 1;

        // j - iの間でベストなペアを探していく
        for( ; j < i; j++, i-- ){
            a[i] = j; a[j] = i;
        }
        i = nextI;
    }

    printf( "%I64d\n", ans );
    for( int i = 0; i <= N; i++ ){
        printf( "%d ", a[i] );
    }
}