постановка задачи следующая:
Xorq изобрел алгоритм шифрования, который широко использует побитовые операции XOR. Этот алгоритм шифрования использует в качестве ключа последовательность неотрицательных целых чисел x1, x2,… xn. Чтобы реализовать этот алгоритм эффективно, Xorq необходимо найти максимальное значение для (a xor xj) для заданных целых чисел a, p и q, таких что p ‹= j‹ = q. Помогите Xorq реализовать эту функцию.
Вход
Первая строка ввода содержит единственное целое число T (1 ‹= T‹ = 6). Далее следуют T-тестовые примеры.
Первая строка каждого тестового примера содержит два целых числа N и Q, разделенных одним пробелом (1 ‹= N‹ = 100 000; 1 ‹= Q‹ = 50 000). Следующая строка содержит N целых чисел x1, x2,… xn, разделенных одним пробелом (0 ‹= xi‹ 2 ^ 15). Каждая из следующих Q строк описывает запрос, состоящий из трех целых чисел ai, pi и qi (0 ‹= ai‹ 2 ^ 15, 1 ‹= pi‹ = qi ‹= N).
Выход
Для каждого запроса выведите максимальное значение для (ai xor xj) такое, что pi ‹= j‹ = qi в одной строке.
int xArray[100000];
cin >>t;
for(int j =0;j<t;j++)
{
cin>> n >>q;
//int* xArray = (int*)malloc(n*sizeof(int));
int i,a,pi,qi;
for(i=0;i<n;i++)
{
cin>>xArray[i];
}
for(i=0;i<q;i++)
{
cin>>a>>pi>>qi;
int max =0;
for(int it=pi-1;it<qi;it++)
{
int t = xArray[it] ^ a;
if(t>max)
max =t;
}
cout<<max<<"\n" ;
}
Никакие другие предположения не могут быть сделаны кроме тех, которые указаны в тексте задачи (числа не сортируются). Код функциональный, но недостаточно быстрый; действительно ли чтение из стандартного ввода так медленно или что-то еще мне не хватает?
cinиoperator>>может быть медленным, но также может быть форматированный вывод (cout << ...). Вы, вероятно, обнаружите, что большую часть времени эта функция запускает только с вводом и выводом, а не с битовыми манипуляциями. - person the_mandrill schedule 28.11.2013max{a xor x_(p-1); a xor x_(q-1)}- person ogni42 schedule 28.11.2013