Некоторые общие замечания о вашей программе (не связанные с проблемой памяти, но могут помочь решить ее):
import java.util.Scanner;
public class FLIPCOIN4 {
Ваше имя класса немного странное - было ли это как-то предписано задачей?
(В Java для имени класса обычно используется случай верблюда. FlipCoin будет примером здесь.)
public static void main(String args[])
{
Вы выполняете всю свою обработку внутри этого действительно большого метода. Лучше структурируйте свой код, поместите его в несколько методов, каждый из которых имеет только одну задачу.
Scanner in = new Scanner(System.in);
//take N = no of coins, Q = no of commands as input
String s = in.nextLine();
String[] str = s.split(" ");
int N = Integer.parseInt(str[0]);
int Q= Integer.parseInt(str[1]);
Класс Scanner имеет больше методов, чем только nextLine() - если вы будете использовать напрямую nextInt, ваша программа будет короче на совсем немного.
int[] output = new int[Q];
Для чего вам нужен массив output? Вы можете просто вывести каждое число, как только произведете. Это сэкономит вам 200 кБ (если их тестовый ввод действительно Q = 50000).
int[] input;
//input - array of integers (one integer for 32 coins)
if(N%32>0)
input = new int[N/32 + 1];
else
input = new int[N/32];
Вы могли бы использовать [(N-1)/32 +1] здесь и избежать двух случаев, но я не уверен, что это действительно более читабельно.
Массив input имеет неправильное имя: он не является вводом, но представляет текущее состояние монет.
//initialize to 0 = tails
for(int i=0;i<input.length;i++)
{
input[i] = 0;
}
Элементы массива автоматически инициализируются с помощью 0 (или '\0' или 0.0 или null), поэтому этот цикл совершенно не нужен.
int out = 0;
int temp1 = 0;
int temp2 = 0;
int command = 0;
int RangeL = 0;
int RangeR = 0;
Большинство этих переменных будет лучше объявлено (и инициализировано) там, где они впервые используются.
//looping over all Q commands
while(Q>0) {
s = in.nextLine();
str = s.split(" ");
//command - command code
//RangeL,RangeR - range of coins which are affected
command = Integer.parseInt(str[0]);
RangeL = Integer.parseInt(str[1]);
RangeR = Integer.parseInt(str[2]);
Как уже было сказано, вы могли бы использовать in.nextInt() здесь так же легко.
Я также думаю, что метод s.split каждый раз создает новый шаблон регулярных выражений, который не занимает много времени, но все же является излишним.
// command==0 => if coins are to be flipped
А для команд вам на самом деле не нужно разбирать его как int, использование сравнения строк тоже подойдет.
if(command==0) {
//if the coins range is over multiple numbers in array input[]
if(RangeR/32>RangeL/32) {
if(RangeL%32==0)
Вы используете четыре цифры RangeR/32, RangeL/32, RangeR%32 и RangeL%32 снова и снова. Присвойте им правильные переменные (или даже константы с final) - это, во-первых, сделает вашу программу немного быстрее и (что более важно) более разборчивой, если вы используете правильные имена.
input[RangeL/32] = input[RangeL/32] ^ -1;
else if(RangeL%32==1)
input[RangeL/32] =
input[RangeL/32] ^ Integer.MAX_VALUE;
else
input[RangeL/32] =
input[RangeL/32] ^ (int)Math.pow(2, 32-(RangeL%32));
Не используйте Math.pow для целочисленного возведения в степень с малой степенью двойки.
2 x доступен для записи как 1 << x (если 0 <= x <32). </p>
if(RangeR%32==0)
input[RangeR/32] = input[RangeL/8] ^ Integer.MIN_VALUE;
else
input[RangeR/32] =
input[RangeR/8] ^
(Integer.MIN_VALUE
+ ( Integer.MAX_VALUE +1-
(int) Math.pow(2, 31-(RangeL%32))));
Да, это жестокая формула. Знаете ли вы, что Integer.MAX_VALUE + 1 == Integer.MIN_VALUE?
if(RangeR/32 - RangeL/32 > 1) {
for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
input[i] = input[i] ^ -1;
}
}
Ваш цикл будет работать так же без проверки if раньше (тогда это будет пустой цикл).
}//if the coins range is contained in one single integer in input[]
else if(RangeR/32==RangeL/32) {
Этот комментарий выглядит так, как будто он относится к закрывающей скобке, тогда как в действительности он относится к следующему if.
if(RangeL%32==0 && RangeR%32==0)
input[RangeL/32] = input[RangeL/32] ^
Integer.MIN_VALUE;
else if(RangeL%32==0 && RangeR%32==1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MIN_VALUE + (int) Math.pow(2, 30));
else if(RangeL%32==0 && RangeR%32 >1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MIN_VALUE + Integer.MAX_VALUE +1 -
(int) Math.pow(2, 31-(RangeR%32)));
else if(RangeL%32==1 && RangeR%32 ==1)
input[RangeL/32] = input[RangeL/32] ^
(int) Math.pow(2, 30);
else if(RangeL%32==1 && RangeR%32 >1)
input[RangeL/32] = input[RangeL/32] ^
(Integer.MAX_VALUE +1 -
(int) Math.pow(2, 31-(RangeR%32)));
else
input[RangeL/32] = input[RangeL/32] ^
((int) Math.pow(2, 32-(RangeL%32)) -
(int) Math.pow(2, 31-(RangeR%32)) );
Как было сказано ранее: поместите это в другой метод и не используйте Math.pow.
}
}// command==1 => no of heads is to be reported
else if(command==1) {//if the coins range is contained in a single integer
if(RangeR/32 == RangeL/32) {
temp1 = input[RangeL/32]<< RangeL%32;
temp1 = temp1 >>> RangeL%32;
temp1 = temp1 >>> (31 - RangeR%32);
temp1 = temp1 << (31 - RangeR%32);
Ах, вы знаете, как сдвинуть бит: -)
Вместо того, чтобы сдвигать биты, вы могли бы их тоже замаскировать. final int mask = 1<<(32-RangeL%32) - 1<<(31-RangeR%32) или аналогичный, а затем temp1 = mask & input[RangeL/32].
output[out] = Integer.bitCount(temp1);
}
//if the coins range is over multiple numbers in array input[]
else if(RangeR/32>RangeL/32) {
temp1 = input[RangeL/32]<< RangeL%32;
temp1 = temp1 >>> RangeL%32;
temp2 = input[RangeL/32] >>> (31 - RangeR%32);
temp2 = temp2 << (31 - RangeR%32);
output[out] =
Integer.bitCount(temp1)+ Integer.bitCount(temp2);
}
if(RangeR/32 - RangeL/32 > 1) {
for(int i=RangeL/32+1; i <RangeR/32 ; i++) {
output[out] = output[out] + Integer.bitCount(input[i]);
}
}
То, что я сказал ранее, также применимо к этому циклу.
out++;
В этот момент вы можете вывести результат, но не иметь этого массива вообще.
}
Q--;
}
for(int i =0;i<out;i++) {
System.out.println(output[i]);
}
(Этот вывод не был бы необходим тогда.)
}
}
Еще одна вещь, о которой стоит подумать: если бы вы заказали биты наоборот, вам не пришлось бы везде использовать эти вычитания в показателях степени.
А использование чего-то вроде java.util.BitSet сделает всю вашу программу очень короткой, поскольку она выполняет всю битовую логику за вас.