You are viewing a single comment's thread. Return to all comments →
This times out on the last 4 test cases in Java, but passes when written in c++, is there anything obviously wrong with something I'm doing in Java?
import java.util.*; public class PrimeXor { private static long mod = 1000000007; private static List<Integer> getPrimes(int max) { List<Integer> prime_list = new ArrayList<>(); boolean[] primes = new boolean[max]; Arrays.fill(primes, true); primes[0] = false; primes[1] = false; for (int i = 0; i < primes.length; i++) { if (primes[i]) { prime_list.add(i); for (int inner = i * 2; inner < primes.length; inner += i) { primes[inner] = false; } } } return prime_list; } public static void main(String[] args) { List<Integer> primes = getPrimes(8192); Scanner scn = new Scanner(System.in); int queries = scn.nextInt(); for (int query = 0; query < queries; query++) { int values = scn.nextInt(); long dp[][] = new long[1000][8192]; long element_counts[] = new long[3500]; for (int value = 0; value < values; value++) { element_counts[scn.nextInt() - 3500]++; } dp[0][0] = (element_counts[0] + 2) / 2; dp[0][3500] = (element_counts[0] + 1) / 2; for (int numbers = 1; numbers < dp.length; numbers++) { for (int primes_nums = 0; primes_nums < dp[numbers].length; primes_nums++) { dp[numbers][primes_nums] = (((dp[numbers - 1][primes_nums]) % mod) * (((element_counts[numbers] + 2) / 2) % mod)) + ((dp[numbers - 1][(numbers + 3500) ^ primes_nums] % mod) * (((element_counts[numbers] + 1) / 2) % mod)); } } long total_sum = 0; for (Integer prime : primes) { total_sum = ((total_sum % mod) + (dp[dp.length - 1][prime] % mod)) % mod; } System.out.println(total_sum); } } }
Seems like cookies are disabled on this browser, please enable them to open this website
Prime XOR
You are viewing a single comment's thread. Return to all comments →
This times out on the last 4 test cases in Java, but passes when written in c++, is there anything obviously wrong with something I'm doing in Java?