Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
maksvolf96
3 / 3 / 0
Регистрация: 18.05.2014
Сообщений: 202
#1

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

21.01.2015, 01:11. Просмотров 502. Ответов 6
Метки нет (Все метки)

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

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

Входные данные
В первой строке входных данных записано два числа 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
 
}
Прошу указать косяк или написать нормальный код через цельный бинарник. Спасибо
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2015, 01:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Ошибка во время выполнения программы (C++):

Ошибка во время выполнения программы. - C++
Здравствуйте, помогите, пожалуйста, разобраться. Пытаюсь сдать задачу, из 27 тестов в трех - ошибка во время выполнения программы. ...

Укажите где ошибка (ошибка во время выполнения программы) - C++
Здравствуйте, помогите пожалуйста найти ошибки в коде которые возникаю при выполнении программы Картинка с ошибкой внизу поста. Код: ...

Ошибка во время выполнения программы (размещения с повторениями) - C++
Давно я не заходил на прекрасный форум...Надеюсь, найдутся люди, которые смогут помочь... Итак, задача: Даны N целых чисел x1,...

Во время выполнения программы результат не выводится. Где ошибка? - C++
Здравствуйте. Помогите, пожалуйста, найти ошибку в коде. Задание звучит так. Дан массив 4х5, нужно создать одномерный массив и...

Время выполнения программы - C++
Здравствуйте.Я до сих пор новичок в программировании,сразу скажу,и тонкостей не знаю. Собрал я тут программу с использованием CUDA.И...

Посчитать время выполнения программы - C++
В среде visual studio 2012 можно? или в коде написать что нужно, подскажите

6
rikimaru2013
C++ Game Dev
2468 / 1137 / 240
Регистрация: 30.11.2013
Сообщений: 3,701
21.01.2015, 03:36 #2
Цитата Сообщение от maksvolf96 Посмотреть сообщение
Прошу указать косяк
C++
1
2
 for(int i=0;i<1000000;i++)
        contV.push_back(cnt);
Мне просто интересно зачем 8ГБ ОЗУ вам.
0
maksvolf96
3 / 3 / 0
Регистрация: 18.05.2014
Сообщений: 202
21.01.2015, 20:05  [ТС] #3
Что не так? Это такой способ решения, сложность получается O(N*K) + logN , вроде того, по времени проходит, поясните, я не так давно на ++
0
zss
Модератор
Эксперт С++
6715 / 6277 / 2092
Регистрация: 18.12.2011
Сообщений: 16,376
Завершенные тесты: 1
21.01.2015, 20:10 #4
C++
1
2
vector <container> contV(100000);
fill(contV.begin(),100000,cnt);
А в качестве m1 и m2 лучше взять multiset.
Они будут сразу упорядоченны.
Поиск вести функцией find.
Вот пример из Мюссера.
Подробнее не могу - гриппом болею
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 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;
}
0
castaway
Эксперт С++
4920 / 3028 / 372
Регистрация: 10.11.2010
Сообщений: 11,085
Записей в блоге: 10
Завершенные тесты: 1
21.01.2015, 20:11 #5
Цитата Сообщение от maksvolf96 Посмотреть сообщение
Что не так?
Зачем тебе миллион одинаковых объектов? Ты уверен что память под них выделяется успешно?
0
rikimaru2013
C++ Game Dev
2468 / 1137 / 240
Регистрация: 30.11.2013
Сообщений: 3,701
21.01.2015, 20:24 #6
Цитата Сообщение от maksvolf96 Посмотреть сообщение
Это такой способ решения
Если это нужно для решения задачи - решение не правильное. Если это способ тестирования - перебор! Создайте ну 500-1000 объектов - сделайте замер времени вначале перед вызовом метода поиска и после. Узнаете за сколько он отработал - запустите несколько раз. Профит.

P.S. В код не вникал я уверен никто как и я после строки в 8 ГБ ОЗУ.
0
maksvolf96
3 / 3 / 0
Регистрация: 18.05.2014
Сообщений: 202
21.01.2015, 21:04  [ТС] #7
По поводу 8 гб озу, в задаче нет ограничения на элементы массива, поэтому я взял что-то большое. Вообще задачу сдал еще вчера вот таким кодом

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/*#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;
 
 
}
0
21.01.2015, 21:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2015, 21:04
Привет! Вот еще темы с ответами:

Определить время выполнения программы - C++
Господа как засеч време выполнение программы? Заранее всем огромное спасибо!!!

Уменьшить время выполнения программы - C++
#include &lt;iostream&gt; using namespace std; int main() { int n; cin &gt;&gt; n; char mas; int k;

Определить время выполнения программы - C++
Как узнать сколько выполняется программа на С++.Т.е. что бы со всеми результатами,скажем в конце, выводилось еще и ее время выполнения,...

Определить время выполнения программы - C++
В связи с доработкой алгоритма разных прог, иногда необходимо посмотреть на сколько повысилась производительность и уменьшилось время...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru