結果

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