結果

問題 No.130 XOR Minimax
ユーザー testtest
提出日時 2016-02-05 19:20:33
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 25 ms / 5,000 ms
コード長 2,284 bytes
コンパイル時間 470 ms
コンパイル使用メモリ 27,840 KB
実行使用メモリ 4,480 KB
最終ジャッジ日時 2023-10-10 00:10:47
合計ジャッジ時間 1,777 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
4,348 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 2 ms
4,352 KB
testcase_03 AC 1 ms
4,352 KB
testcase_04 AC 12 ms
4,352 KB
testcase_05 AC 18 ms
4,352 KB
testcase_06 AC 17 ms
4,348 KB
testcase_07 AC 20 ms
4,348 KB
testcase_08 AC 20 ms
4,348 KB
testcase_09 AC 5 ms
4,352 KB
testcase_10 AC 7 ms
4,352 KB
testcase_11 AC 22 ms
4,352 KB
testcase_12 AC 3 ms
4,348 KB
testcase_13 AC 18 ms
4,348 KB
testcase_14 AC 25 ms
4,352 KB
testcase_15 AC 2 ms
4,352 KB
testcase_16 AC 18 ms
4,352 KB
testcase_17 AC 18 ms
4,348 KB
testcase_18 AC 20 ms
4,480 KB
testcase_19 AC 23 ms
4,352 KB
testcase_20 AC 12 ms
4,352 KB
testcase_21 AC 25 ms
4,352 KB
testcase_22 AC 6 ms
4,352 KB
testcase_23 AC 3 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0