結果

問題 No.5001 排他的論理和でランニング
ユーザー uafr_csuafr_cs
提出日時 2018-03-16 23:49:11
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,380 ms / 1,500 ms
コード長 1,782 bytes
コンパイル時間 2,347 ms
実行使用メモリ 56,312 KB
スコア 52,421,139
最終ジャッジ日時 2020-03-12 19:40:25
ジャッジサーバーID
（参考情報） 		judge9 /
純コード判定しない問題か言語
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,365 ms
54,308 KB
testcase_01 AC 968 ms
52,296 KB
testcase_02 AC 1,047 ms
56,156 KB
testcase_03 AC 1,175 ms
52,712 KB
testcase_04 AC 1,380 ms
52,340 KB
testcase_05 AC 1,110 ms
56,212 KB
testcase_06 AC 1,176 ms
52,404 KB
testcase_07 AC 1,216 ms
52,216 KB
testcase_08 AC 1,287 ms
56,312 KB
testcase_09 AC 922 ms
49,104 KB
testcase_10 AC 1,044 ms
55,956 KB
testcase_11 AC 1,116 ms
52,304 KB
testcase_12 AC 1,031 ms
52,288 KB
testcase_13 AC 1,303 ms
52,284 KB
testcase_14 AC 1,214 ms
52,332 KB
testcase_15 AC 1,121 ms
52,260 KB
testcase_16 AC 1,023 ms
52,288 KB
testcase_17 AC 1,034 ms
54,220 KB
testcase_18 AC 1,178 ms
52,476 KB
testcase_19 AC 1,104 ms
52,324 KB
testcase_20 AC 1,070 ms
52,600 KB
testcase_21 AC 1,048 ms
52,320 KB
testcase_22 AC 961 ms
52,328 KB
testcase_23 AC 967 ms
50,120 KB
testcase_24 AC 1,028 ms
52,468 KB
testcase_25 AC 1,211 ms
52,200 KB
testcase_26 AC 1,175 ms
52,364 KB
testcase_27 AC 1,060 ms
52,276 KB
testcase_28 AC 1,242 ms
54,184 KB
testcase_29 AC 1,322 ms
52,208 KB
testcase_30 AC 1,023 ms
54,136 KB
testcase_31 AC 1,231 ms
52,324 KB
testcase_32 AC 1,100 ms
52,164 KB
testcase_33 AC 1,356 ms
54,304 KB
testcase_34 AC 1,380 ms
52,640 KB
testcase_35 AC 1,258 ms
52,284 KB
testcase_36 AC 1,338 ms
52,212 KB
testcase_37 AC 1,256 ms
52,632 KB
testcase_38 AC 1,065 ms
52,312 KB
testcase_39 AC 1,070 ms
52,492 KB
testcase_40 AC 1,158 ms
52,492 KB
testcase_41 AC 1,005 ms
54,416 KB
testcase_42 AC 1,134 ms
54,440 KB
testcase_43 AC 1,178 ms
52,672 KB
testcase_44 AC 1,309 ms
52,296 KB
testcase_45 AC 1,363 ms
54,136 KB
testcase_46 AC 1,273 ms
56,112 KB
testcase_47 AC 1,148 ms
52,368 KB
testcase_48 AC 1,106 ms
52,652 KB
testcase_49 AC 1,271 ms
52,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
		
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		final int M = sc.nextInt();
		
		int[] array = new int[N];
		for(int i = 0; i < N; i++){
			array[i] = sc.nextInt();
		}
		Arrays.sort(array);
		
		boolean[] used = new boolean[N];
		
		int count = 0;
		long xor = 0;
		for(int bit = 31; bit >= 0 && count < M; bit--){
			if(((1 << bit) & xor) != 0){ continue; }
			
			int max_index = -1;
			long max_value = -1;
			
			for(int i = 0; i < N; i++){
				if(used[i]){ continue; }
				if(((1 << bit) & array[i]) == 0){ continue; }
				
				if(max_value < array[i]){
					max_index = i;
					max_value = array[i];
				}
			}
			
			if(max_index >= 0){
				used[max_index] = true;
				xor ^= max_value;
				count++;
			}
		}
		
		//System.out.println(xor + " " + count + " : " + Arrays.toString(used));
		for(int i = 0; i < N && count < M; i++){
			if(used[i]){ continue; }
			
			used[i] = true;
			xor ^= array[i];
			count++;
		}
		//System.out.println(xor + " " + count + " : " + Arrays.toString(used));
		
		for(int x = 0; x < 9000000; x++){
			final int fst = (int)(Math.random() * N);
			final int snd = (int)(Math.random() * N);
			if(used[fst] && used[snd]){ continue; }
			if(!used[fst] && !used[snd]){ continue; }
			
			final long next_xor = xor ^ array[fst] ^ array[snd];
			if(next_xor > xor){
				xor = next_xor;
				used[fst] = !used[fst];
				used[snd] = !used[snd];
			}
		}
		
		boolean first = true;
		for(int i = 0; i < N; i++){	
			if(!used[i]){ continue; }
			
			System.out.print((first ? "" : " ") + (array[i]));
			first = false;
		}
		System.out.println();
	}
}
0