Что не так с кодом — флаг RE?

Question

[Elnurhan]

Имеется задача: на вход подаётся файл "input.txt". На первой строке этого файла находится число k, на второй строке дана последовательность чисел, записанных через пробел, числа в дипазоне 0 < n < 99999999. Если в последовательности есть два числа, сумма которых равна k, то в файл "output.txt" записать 1, иначе - 0.

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;


int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  unsigned int k, num, ind=0, mxN=2e6;
  
  unsigned int arr[mxN];
 
  ifstream in("input.txt");
  ofstream out("output.txt");

  in >> k;

  while (in >> num)
  {
    arr[ind] = num;
    ++ind;
  }
  if (!k || !ind) return 0;
  // 2 pointers
  sort(arr, arr+ind);
  int l = 0;
  int r = ind - 1;
  while (l != r)
  {
    if (arr[l] + arr[r] < k) 
    {
      ++l;
    }
    else if (arr[l] + arr[r] > k)
    {
      --r;
    }
    else {
      out << "1";
      out.close();
      return 0;
    }
  }

  out << "0";
  out.close();
  return 0;
}

Написал такое решение. Оно рабочее, но на одном из тестов падает с флагом - RE. С чем это может быть связано?

Comments

[Евгений Шатунов]

Elnurhan ,

но на одном из тестов падает с флагом - RE

Что такое этот флаг RE? Поясни, что это означает, т.к. этот термин не является стандартным и ничего не поясняет в широком смысле.

Answer 1

[Антон Жилин]

unsigned int arr[mxN];
Щито? Огромный массив на стеке, да ещё и переменного размера? Это что угодно, но не код, соответствующий стандарту С++. Вектор надо юзать.

Upd: Тут нужно юзать unordered_set. Считать в него числа, потом пройтись по нему и смотреть, есть ли противоположное число.

Comments

[Elnurhan]

Антон Жилин, программирую на питоне вообще, просто по скорости питон не проходит и вектор тоже. Неизвестно какой длины последовательность, поэтому я завёл массив большого размера. А насчёт размера массива не знал, сейчас сделаю его констатным

[Антон Жилин]

Elnurhan, посмотрел саму задачу, тут нужно юзать unordered_set. Считать в него числа, потом пройтись по нему и смотреть, есть ли противоположное число.

[Антон Жилин]

Elnurhan, не надо вообще новичку использовать сырые массивы. Вектор избавит от пляски на граблях.

[Elnurhan]

Антон Жилин, я использовал вектор изначально, но по времени не проходило

[Антон Жилин]

Elnurhan, потому что перед считыванием чисел надо делать v.reserve(mxN);

[Антон Жилин]

Elnurhan, в любом случае, как я писал выше, тут нужен не вектор (и тем более не массив), а unordered_set

[Евгений Шатунов]

Elnurhan, я не понимаю, зачем тебе вообще что-либо сохранять в вектор/массив/какой-либо контейнер.
По задаче тебе надо вернуть единичку если в цепочке чисел два соседних удовлетворяют условию.
Тебе нужна память только на одно число - на предыдущее.

Сперва из потока читаешь число - условие. Далее читаешь первое число в регистр предыдущего числа.
После этого читаешь текущее число и проверяешь условие на текущем и предыдущем числах.
Если условие не выполнено, предыдущим числом становится текущее и цикл повторяется.
Всё.

[Антон Жилин]

Евгений Шатунов, "соседних" нет в условии

[Евгений Шатунов]

Антон Жилин, и действительно, откуда я там вычитал про соседние.
Тогда, да. Нужен вектор, вставка с сохранением сортировки и бинарный поиск, если найти надо не за N^2.

[Антон Жилин]

Евгений Шатунов, это за N logN (автор такой алгоритм и использует), а за N будет так, как я описал

[Elnurhan]

Антон Жилин, unordered_set хранит уникальные элементы, если не ошибаюсь. Допустим - k = 14, последовательность = 1 7 1 7, то 7 учтётся только один раз и в output.txt запишется 0, хотя должна записаться единица

[Антон Жилин]

Elnurhan, тогда надо ещё считать, сколько раз встретили k/2