Ошибка во время выполнения программы

@maksvolf96 · Регистрация: 18.05.2014

Author24 — интернет-сервис помощи студентам

Здравствуйте, есть задача

Дано два списка чисел, числа в первом списке упорядочены по неубыванию. Для каждого числа из второго списка определите номер первого и последнего появления этого числа в первом списке.

Входные данные
В первой строке входных данных записано два числа N и M (1NM20000 ). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

Выходные данные
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Примеры
входные данные
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
выходные данные
10 10
3 4
7 7
1 2
0

Я решил её путем бинарного поиска первого индекса вхождения и линейного поиска второго индекса конца вхождения , т.к. пока хз как там находить второй индекс через бинарник. Не проходит всего 1 тест и пишет ошибку из заголовка

вот код

C++

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N,K, help;
    cin >> N >> K;
 
    vector <int> m1;
    vector <int> m2;
 
    struct container
    {
        int s;
        int f;
    };
 
    vector <container> contV;
 
    container cnt;
 
    cnt.s=-1;
    cnt.f=-1;
 
    for(int i=0;i<1000000;i++)
        contV.push_back(cnt);
 
 
    for (int i=0;i<N;i++)
    {
        cin >> help;
        m1.push_back(help);
    }
 
    for (int i=0;i<K;i++)
    {
        cin >> help;
        m2.push_back(help);
    }
 
//бинарный поиск для нахождения начального индекса элемента из 2 массива
    for (int v:m2)
    {
        int l=0;
        int r=N-1;
 
        while(l<r)
        {
            int avgI=(l+r)/2;
            if(v>m1[avgI])
               l=avgI+1;
            else
               r=avgI;
        }
        
        if(v==m1[l])
            contV[v].s=l+1;
        else{
            contV[v].s=0;
            contV[v].f=0;
        }
    }
 
//линейных поиск для нахождения конечного индекса элемента из 2 массива
    for (int v:m2)
        for (int i=0;i<m1.size();i++)
        if(v==m1[i])
            contV[v].f=i+1;
 
    for (int v:m2)
        if(contV[v].f!=0)
           cout << contV[v].s << " " <<contV[v].f << endl;
           else cout << 0 << endl;
 
}

Прошу указать косяк или написать нормальный код через цельный бинарник. Спасибо

@rikimaru2013 · 21.01.2015, 03:36

Сообщение от maksvolf96

Прошу указать косяк

C++

1 2	for(int i=0;i<1000000;i++) contV.push_back(cnt);

Мне просто интересно зачем 8ГБ ОЗУ вам.

@maksvolf96 · 21.01.2015, 20:05 **[ТС]**

Что не так? Это такой способ решения, сложность получается O(N*K) + logN , вроде того, по времени проходит, поясните, я не так давно на ++

@zss · 21.01.2015, 20:10

C++

1 2	vector <container> contV(100000); fill(contV.begin(),100000,cnt);

А в качестве m1 и m2 лучше взять multiset.
Они будут сразу упорядоченны.
Поиск вести функцией find.
Вот пример из Мюссера.
Подробнее не могу - гриппом болею

C++

// Finding all anagram groups in a given dictionary of words
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <iterator>
#include <functional>
using namespace std;
 
typedef multimap<string, string> multimap_1;
typedef multimap_1::value_type PS;
typedef multimap_1::const_iterator PSi;
 
typedef pair<PSi, PSi> PPS;
 
int main() {
  cout << "Anagram group finding program:\n"
    << "finds all anagram groups in a dictionary.\n\n";
 
  cout << "First, enter the name of the file containing\n"
       << "the dictionary: " << flush;
  string dictionary_name; 
  cin >> dictionary_name;
  ifstream ifs(dictionary_name.c_str());
  if (!ifs.is_open()) {
    cout << "Eh? Could not open file named "
         << dictionary_name << endl;
    exit(1);
  }
 
  cout << "\nReading the dictionary ..." << flush;
 
  // Copy words from dictionary file to 
  // a multimap:
  typedef istream_iterator<string> string_input;
  multimap_1 word_pairs;
  for (string_input in(ifs); in != string_input(); ++in) {
    string word = *in;
    sort(word.begin(), word.end());
    word_pairs.insert(PS(word, *in));
  } 
 
  cout << "\nSearching " << word_pairs.size() 
    << " words for anagram groups..." << flush;
 
  // Set up the map from anagram group sizes to lists of
  // groups of that size:
  typedef map<int, list<PPS>, greater<int> > map_1;
  map_1 groups;
 
  // Find all the anagram groups and save their 
  // positions in the groups map:
  cout << "\n\nThe anagram groups are: " << endl;
  PSi j = word_pairs.begin(), finis = word_pairs.end(), k;
  while (true) {
    // Make j point to the next anagram 
    // group, or to the end of the multimap:
    j = adjacent_find(j, finis,
                      not2(word_pairs.value_comp()));
    if (j == finis) break;
    
    k = find_if(j, finis, 
                bind1st(word_pairs.value_comp(), *j));
    multimap_1::size_type n = distance(j, k);
    if (n > 1)
      // Save the positions j and k delimiting the anagram
      // group in the list of groups of size n:
      groups[n].push_back(PPS(j, k)); 
 
    // Prepare to continue search at position k:
    j = k;
  }
 
  // Iterate through the groups map to output the anagram
  // groups in order of decreasing size:
  map_1::const_iterator m;
  for (m = groups.begin(); m != groups.end(); ++m) {
 
    cout << "\nAnagram groups of size "
      << m->first << ":\n";
 
    list<PPS>::const_iterator l;
    for (l = m->second.begin(); 
         l != m->second.end(); ++l) {
      cout << "   ";
      j = l->first;  // Beginning of the anagram group 
      k = l->second; // End of the anagram group
      for (; j != k; ++j)
        cout << j->second << " ";
      cout << endl;
    }
  }
  return 0;
}

@castaway · 21.01.2015, 20:11

Сообщение от maksvolf96

Что не так?

Зачем тебе миллион одинаковых объектов? Ты уверен что память под них выделяется успешно?

@rikimaru2013 · 21.01.2015, 20:24

Сообщение от maksvolf96

Это такой способ решения

Если это нужно для решения задачи - решение не правильное. Если это способ тестирования - перебор! Создайте ну 500-1000 объектов - сделайте замер времени вначале перед вызовом метода поиска и после. Узнаете за сколько он отработал - запустите несколько раз. Профит.

P.S. В код не вникал я уверен никто как и я после строки в 8 ГБ ОЗУ.

@maksvolf96 · 21.01.2015, 21:04 **[ТС]**

По поводу 8 гб озу, в задаче нет ограничения на элементы массива, поэтому я взял что-то большое. Вообще задачу сдал еще вчера вот таким кодом

C++

/*#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N,K, help;
    cin >> N >> K;
 
    vector <int> m1;
    vector <int> m2;
 
    struct container
    {
        int s;
        int f;
    };
 
    vector <container> contV;
 
    container cnt;
 
    cnt.s=-1;
    cnt.f=-1;
 
    for(int i=0;i<1000000;i++)
        contV.push_back(cnt);
 
 
    for (int i=0;i<N;i++)
    {
        cin >> help;
        m1.push_back(help);
    }
 
    for (int i=0;i<K;i++)
    {
        cin >> help;
        m2.push_back(help);
    }
 
//бинарный поиск для нахождения начального индекса элемента из 2 массива
    for (int v:m2)
    {
        int l=0;
        int r=N-1;
 
        while(l<r)
        {
            int avgI=(l+r)/2;
            if(v>m1[avgI])
               l=avgI+1;
            else
               r=avgI;
        }
 
        if(v==m1[l])
            contV[v].s=l+1;
        else{
            contV[v].s=0;
            contV[v].f=0;
        }
    }
 
//линейных поиск для нахождения конечного индекса элемента из 2 массива
    for (int v:m2)
        for (int i=0;i<m1.size();i++)
        if(v==m1[i])
            contV[v].f=i+1;
 
    for (int v:m2)
        if(contV[v].f!=0)
           cout << contV[v].s << " " <<contV[v].f << endl;
           else cout << 0 << endl;
 
}
*/
 
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N,K, help;
    cin >> N >> K;
 
    vector <int> m1;
    vector <int> m2;
 
    struct container
    {
        int s;
        int f;
    };
 
    vector <container> contV(K);
 
    container cnt;
 
    for (int i=0;i<N;i++)
    {
        cin >> help;
        m1.push_back(help);
    }
 
    for (int i=0;i<K;i++)
    {
        cin >> help;
        m2.push_back(help);
    }
 
//бинарный поиск для нахождения начального индекса элемента из 2 массива
int k1=-1;
    for (int v:m2)
    {
        int l=0;
        int r=N-1;
 
        while(l<r)
        {
            int avgI=(l+r)/2;
            if(v>m1[avgI])
               l=avgI+1;
            else
               r=avgI;
        }
 
        if(v==m1[l]){
                k1++;
            contV[k1].s=l+1;
        }
        else{
            k1++;
            contV[k1].s=0;
            contV[k1].f=0;
        }
    }
 
//линейных поиск для нахождения конечного индекса элемента из 2 массива
int k2=-1;
 
    for (int v:m2)
    {
        int ff=0;
        for (int i=0;i<m1.size();i++)
        {
            if(v==m1[i]){
                    ff=i+1;
            }
        }
           if(ff!=0)
           {
            k2++;
            contV[k2].f=ff;
           }
 
           else{
            k2++;
           }
    }
    for (container st:contV)
        if (st.f!=0)
        cout << st.s << " " << st.f << endl;
        else
            cout << 0 << endl;
 
 
}

@maksvolf96 3 / 3 / 2 Регистрация: 18.05.2014 Сообщений: 203
	21.01.2015, 20:05 [ТС]	3
	Что не так? Это такой способ решения, сложность получается O(N*K) + logN , вроде того, по времени проходит, поясните, я не так давно на ++ 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	21.01.2015, 20:11	5
	Сообщение от maksvolf96 Что не так? Зачем тебе миллион одинаковых объектов? Ты уверен что память под них выделяется успешно? 0

@rikimaru2013 2549 / 1208 / 358 Регистрация: 30.11.2013 Сообщений: 3,826
	21.01.2015, 20:24	6
	Сообщение от maksvolf96 Это такой способ решения Если это нужно для решения задачи - решение не правильное. Если это способ тестирования - перебор! Создайте ну 500-1000 объектов - сделайте замер времени вначале перед вызовом метода поиска и после. Узнаете за сколько он отработал - запустите несколько раз. Профит. P.S. В код не вникал я уверен никто как и я после строки в 8 ГБ ОЗУ. 0

	21.01.2015, 21:04