結果
問題 | No.130 XOR Minimax |
ユーザー | test |
提出日時 | 2016-02-05 19:20:33 |
言語 | C++11 (gcc 11.4.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 12 ms
6,940 KB |
testcase_05 | AC | 18 ms
6,940 KB |
testcase_06 | AC | 16 ms
6,940 KB |
testcase_07 | AC | 19 ms
6,944 KB |
testcase_08 | AC | 19 ms
6,940 KB |
testcase_09 | AC | 4 ms
6,940 KB |
testcase_10 | AC | 6 ms
6,944 KB |
testcase_11 | AC | 20 ms
6,944 KB |
testcase_12 | AC | 3 ms
6,944 KB |
testcase_13 | AC | 17 ms
6,940 KB |
testcase_14 | AC | 24 ms
6,944 KB |
testcase_15 | AC | 1 ms
6,944 KB |
testcase_16 | AC | 18 ms
6,940 KB |
testcase_17 | AC | 18 ms
6,940 KB |
testcase_18 | AC | 19 ms
6,944 KB |
testcase_19 | AC | 22 ms
6,944 KB |
testcase_20 | AC | 11 ms
6,940 KB |
testcase_21 | AC | 24 ms
6,940 KB |
testcase_22 | AC | 5 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
コンパイルメッセージ
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]); } | ~~~~~^~~~~~~~~~~~~
ソースコード
#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; }