結果

問題 No.130 XOR Minimax
ユーザー test
提出日時 2016-02-05 19:20:33
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 2,284 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 25,088 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-12 22:37:02
合計ジャッジ時間 1,380 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:96:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   96 |         scanf("%d", &a_len);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:97:46: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |         for(int i = 0; i < a_len; ++i){ scanf("%d", &a[i]); }
      |                                         ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
int const M = (1 << 17); 
void merge_down(int (&a)[M], int l, int r){
    if(l >= r || 0 > l || M <= r){ return; }
    static int temp[M]; 
    int al, ar, bl, br, i, j, k;
    for(int seg = 2, len = 2 * (r-l+1); seg < len; seg <<= 1){ 
        al = l;     ar = al + seg/2 - 1;
        bl = ar+1;  br = bl + seg/2 - 1;
        for( ; ; al += seg, ar += seg, bl += seg, br += seg){
            ar = ((ar < r)? ar : r); 
            bl = ((bl < r)? bl : r);
            br = ((br < r)? br : r);
            if(ar >= bl){ break; } 
            for(i = al, j = bl, k = al; k <= br; ++k){
                if(i > ar){
                    temp[k] = a[j]; ++j;
                }else if(j > br){
                    temp[k] = a[i]; ++i;
                }else if(a[i] <= a[j]){ // 注3
                    temp[k] = a[i]; ++i;
                }else{
                    temp[k] = a[j]; ++j;
                }
            }
            for(k = al; k <= br; ++k){ a[k] = temp[k]; }
        }
    }
}
int a[M]; 
static int r[31]; 
void init(){
    for(int i = 0; i < 31; ++i){ r[i] = (1 << i); }
}
int getMaxR(int n){
    if(0 == n){ return 0; }
    if(1 == n){ return 1; }
    int i = 16, k = 8; 
    int R; 
    for( ; 0 != k; k >>= 1){
        R = r[i]; 
        if(n == R){ return R; }
        if(n > R){ i += k; }else{ i -= k; }
    }
    R = r[i]; 
    return ( (n >= R)? R : (R >> 1) ); 
}
int min_max(int first, int last, int m){
    if(first == last){ return 0; }
    int R = getMaxR(a[last] & m); 
    int k = getMaxR(last - first), j = first, n; 
    for( ; 0 != k; k >>= 1){
        if(last  < j){ j -= k; continue; }
        if(first > j){ j += k; continue; }
        n = a[j] & m; 
        if(n == R){ break; }
        if(n < R){ j += k; }else{ j -= k; }
    }
    if(first > j){ j = first; }
    if(last  < j){ j = last; }
    if((a[j] & m) < R){ ++j; }
    if(first == j){ 
        return min_max(first, last, R - 1); 
    }else{ 
        int temp1 = min_max(first, j - 1, R - 1), temp2 = min_max(j, last, R - 1); 
        return R + ((temp1 < temp2)? temp1 : temp2); 
    }
    return 0; 
}
int min_max(int a_len){
    if(0 >= a_len){ return 0; }
    init(); 
    merge_down(a, 0, a_len - 1); 
    { 
        int k = 0, m = a[k]; 
        for(int i = 0; i < a_len; ++i){ 
            if(m == a[i]){ continue; }
            ++k; m = a[k] = a[i]; 
        }
        a_len = k + 1; 
    } 
    return min_max(0, a_len - 1, (1 << 30) + ((1 << 30) - 1)); 
}
#define set(n) a[a_len] = n; ++a_len
int main(int argc, char *argv[]){
    int a_len = 0; 
    scanf("%d", &a_len); 
    for(int i = 0; i < a_len; ++i){ scanf("%d", &a[i]); }
    printf("%d\n", min_max(a_len)); 
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0