Непонятный Stack Overflow

@ZaMaZaN4iK · Регистрация: 24.06.2012

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

Здравствуйте, уважаемые форумчане.Столкнулся с непонятной мне проблемой при решении одной лёгкой олимпидной задачи.

Вот условие задачи:
Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.

Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.

Требуется написать программу, которая решает данную задачу.
Входные данные

Первая строка входного файла INPUT.TXT содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел, не превышающих по модулю 109. Все числа в строке разделены пробелом.
Выходные данные

В выходной файл OUTPUT.TXT выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.

вот код:

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
#include <cstdio>
#include <iostream>
#include <algorithm>
 
 
using namespace std;
 
 
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    long long digit,temp=1,count=1,i,n,arr[200000],vyvod[200000];
    scanf("%I64d",&n);
    for(i=0;i<n;++i)
    {
        scanf("%I64d",&arr[i]);
        vyvod[i]=arr[i];
    }
    sort(arr,arr+n);
    digit=arr[0];
    for(i=0;i<n-1;++i)
    {
        if(arr[i] == arr[i+1])
            ++temp;
        else
        {
            if(temp>count)
            {
                digit=arr[i];
                count=temp;
            }
            temp=1;
        }
    }
    for(i=0;i<n;++i)
        if(vyvod[i] != digit)
            printf("%I64d ",vyvod[i]);   
    for(i=0;i<count;++i)
        printf("%I64d ",digit);
    system("pause");
    return 0;
}

Так вот, решение простое вроде я придумал - вводим массив, дублируем его.Потом первый массив сортируем sort() из STL, потом ищем в отсортированном массиве минимальное число, которое встречается наибольшее число раз, и записываем в переменные, что это за число и сколько раз встречалось.Потом выводим сначала из исходного массива по порядку все числа кроме найденного, а потом уже выводим нужное кол-во раз найденное число.

Но вот в чём проблема - при запуске программы сразу же программа вылетает.Компилировал как g++, так и компилятором от MSVS 2010(забыл как он называется).Ошибка одна и та же - переполнение стека.Но где??? и оно идет в самом начале программы.Если размеры исходных массивов ставить не 200000, а допусти м 200, то ошибки нет.Но как размер массива влияет на стек?Первый раз с таким сталкиваюсь - я не думал, что массив сложно такого размера создать.

Прошу вас, помогите понять, в чём суть данной проблемы.

Заранее спасибо.

@stima · 28.04.2013, 00:51

Это ограничение стека http://www.cs.nyu.edu/exact/co... erflow.txt.
Создайте массивы на куче или расширьте стек.

@ZaMaZaN4iK · 28.04.2013, 01:13 **[ТС]**

да понимаете, пробовал увеличить просто стек так:

C++
1
#pragma comment(linker, "/STACK:32777216")

(вроде это так делается)
Не помогает

Добавлено через 19 минут
вот ещё что заметил - если юзать 2 vector, то ошибка пропадает.Но после использования sort() из STL, сортировка весь массив почему то запоняет нулями, а все значения, которые я туда записал, она заменяет на 0(само собой, ввод в вектор через cin).Чудеса одним словом.Но если писать квиксорт самому, и потом им сортить вектора, то всё проходит.Но мне этот вариант решения не подходит - мне нужно именно с простыми массивами.

@kravam · 28.04.2013, 08:30

Вот твой код, я его упростил.

C++
1
2
3
4
5
6
7
8
9
#include <stdio.h>
 
int main()
{
    printf ("%d\n", sizeof(long long));
    long long arr[200000], vyvod[200000];
    getchar ();
    return 0;
}

long long это восемь байт, вот у тебя под массивы занято 3200000 байт, всё плохо, короче. Поэтому увеличиваем размер стека. В g++ это можно сделать используя такую опцию:

C++
1
-Wl,--stack,<новый размер стека>

Как в MSVS это сделать, не знаю.

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

Добавлено через 1 минуту

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

Но как размер массива влияет на стек?

Так просто ж всё. Где по твоему массив размещается? В стеке и размещается.

@diagon · 28.04.2013, 11:27

Можно попробовать вынести массивы в глобальную область видимости.

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

по модулю 109

109 или 10^9?

В любом случае, зачем вам long long, если все влазит в обычный int?

@ZaMaZaN4iK · 28.04.2013, 19:54 **[ТС]**

diagon, просто в олимпиадном программировании обычно юзают сразу long long и не парятся.Прошу прощения, не досмотрел про условие - там 10 в 9 степени, а не 109.Сейчас попробую сделать массивы глобальными, хотя навряд ли это поможет.

kravam, да-да, я знаю, что long long это 8 байт.Но разве нельзя делать массивы таких размеров?Спасибо, теперь понял, что массивы в стеке размещаются.Но вот вопрос - на олимпиадах дают ограничения 128(256 мб).Тогда как их занять, если стек такие капризы выкидывает?

@DU · 28.04.2013, 19:57

взяли и засрали стек на ровном месте.
достаточно воспользоваться каким-нибудь вектором ну или динамически выделять память на худой конец.

@ZaMaZaN4iK · 28.04.2013, 20:02 **[ТС]**

DU, вектор заполнять нужно юзать cin вместо scanf, а он намного медленнее scanf(ну или scanfить во временную переменную, а потом в вектор загонять, а это всё время.А память выделяется сразу так много чтобы сразу знать, сколько прога памяти жрёт.Это же олимпиалная задача, не реальная программа.Понятно, что если бы я писал приложение, то я бы делал совсем по-другому.

@DU · 28.04.2013, 20:07

вероятно от незнания вы так говорите. почему вектор нужно как-то по особенному заполнять?

C++
1
2
3
4
5
6
7
8
std::vector<long long> v(200000);
long long* arr = &v[0]
все. дальше работаем как и раньше.
единственная просадка тут - это то, что в векторе данные инициализируются.
если не хотим это делать, то
long long* arr = new long long[200000];
дальше не забыть только удалить. если фичами нового стандарта воспользоваться,
то там спартпоинтеры заточены под автоудаление.

@ZaMaZaN4iK · 28.04.2013, 20:10 **[ТС]**

diagon, помогло!!! Помогло сделать массивы глобальными.Но почему? Расскажите пожалуйста, а то я совсем не разбираюсь в тонкостях программирования

Добавлено через 1 минуту
DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++...

@diagon · 28.04.2013, 20:21

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

Но почему?

Потому что глобальные массивы расположены не на стеке, и для них нет таких суровых ограничений на размер.
Можно было еще попробовать сделать массив static'ом, это тоже должно помочь.

@ZaMaZaN4iK · 28.04.2013, 20:24 **[ТС]**

diagon, а где расположены глобальные массивы?

@kravam · 28.04.2013, 20:43

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

DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++...

Да можно всяко, но от некоторых решений бросает в дрожь. Итак, решено НА ВСЯКИЙ СЛУЧАЙ иметь большие массивы? Получите...

C++
1
2
3
4
5
6
7
8
#include <stdio.h>
long long arr_0 [200000], arr_1 [200000], arr_2 [200000];
 
int main()
{
  getchar ();
  return 0;
}

Добавлено через 6 минут
А находятся эти массивы в области памяти, которую занимает секция неициализируемых переменых. Короче компилятор создаёт экзешник с разными секциями, одна из которых имеет имя .bss- это секция с неициализируемыми переменными. Но это не стандарт, насколько я знаю, просто так работает g++. При запуске программы секции проецируются в память и эта секция тоже. Вот в ней эти глобальные массивы и лежат. Если ты объявишь другие неициализированные переменные, они тоже будут в этой секции.

@diagon · 28.04.2013, 20:49

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

diagon, а где расположены глобальные массивы?

В .global секции. Ну, это уже уровень ассемблера.
Если вкратце, то они одни на всю программу, за счет этого у них дешевая инициализация. А вот локальные массивы заново создаются при каждом вызове функции (в данном случае при входе в main).

@ZaMaZaN4iK · 28.04.2013, 21:02 **[ТС]**

kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.То есть если глобальная переменная инициализирована, то она помещается в стек.И так же справедливо, что если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?

Добавлено через 9 минут
Всем спасибо за ответы!

@kravam · 28.04.2013, 21:30

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

kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.

ну да

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

То есть если глобальная переменная инициализирована, то она помещается в стек.

Нет. Если глобальная переменная инициализирована, то она помещается не в .bss и не в стек, а- в секцию с инициализированными данными. g++ обзывает эту секцию .data и во время работы ты работаешь именно с этой областью памяти.

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

если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял?

В стек. Все локальные переменные, независимо от того, инициализированы они или нет, помещаются в стек. И ты работаешь со стеком.

//++++++++++++++++++++++++++++++++++++++++ ++++

Но тут есть одна факультативная тонкость и она касается локальных переменных. Дело в том, что коль скоро они инициализированы, то эта инициализация сохраняется и тогда, когда программа не работает.

Ну просто. Пусть есть локальная переменная x:

C++
1
int x= 2;

Программа начинает работать и под эту переменную, коль скоро она локальна, выделяется область в стеке. Но! Где-то же эта двойка хранится, когда программа не работает! Где? А вот, тоже где-то в одной из секций, может даже в той же .data выделяются 4 байта и там лежит двойка. Но, повторю, это вопрос хранения значения локальной переменной в экзешнике. Во время работы ты работаешь с глобальными или с локальными переменными, которые (если они локальные) находятся в стеке.

Ну а глобальные в зависимости от инициализации в одной из секций, повторюсь, на имена секций стандарта, кажись нет. Просто их так обзывает g++.

@ZaMaZaN4iK · 28.04.2013, 22:32 **[ТС]**

kravam, большое спасибо - теперь понял, наконец-то, как оно всё хранится.

Новые блоги и статьи Все статьи Все блоги /
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@stima 503 / 352 / 94 Регистрация: 22.03.2011 Сообщений: 1,112
	28.04.2013, 00:51
	Это ограничение стека http://www.cs.nyu.edu/exact/co... erflow.txt. Создайте массивы на куче или расширьте стек. 1

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 19:54 [ТС]
	diagon, просто в олимпиадном программировании обычно юзают сразу long long и не парятся.Прошу прощения, не досмотрел про условие - там 10 в 9 степени, а не 109.Сейчас попробую сделать массивы глобальными, хотя навряд ли это поможет. kravam, да-да, я знаю, что long long это 8 байт.Но разве нельзя делать массивы таких размеров?Спасибо, теперь понял, что массивы в стеке размещаются.Но вот вопрос - на олимпиадах дают ограничения 128(256 мб).Тогда как их занять, если стек такие капризы выкидывает? 0

@DU 1500 / 1146 / 165 Регистрация: 05.12.2011 Сообщений: 2,279
	28.04.2013, 19:57
	взяли и засрали стек на ровном месте. достаточно воспользоваться каким-нибудь вектором ну или динамически выделять память на худой конец. 1

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 20:02 [ТС]
	DU, вектор заполнять нужно юзать cin вместо scanf, а он намного медленнее scanf(ну или scanfить во временную переменную, а потом в вектор загонять, а это всё время.А память выделяется сразу так много чтобы сразу знать, сколько прога памяти жрёт.Это же олимпиалная задача, не реальная программа.Понятно, что если бы я писал приложение, то я бы делал совсем по-другому. 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 20:10 [ТС]
	diagon, помогло!!! Помогло сделать массивы глобальными.Но почему? Расскажите пожалуйста, а то я совсем не разбираюсь в тонкостях программирования Добавлено через 1 минуту DU, спасибо.Действительно не знал, что так можно.Эхх, необьятный С++... 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 20:24 [ТС]
	diagon, а где расположены глобальные массивы? 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 21:02 [ТС]
	kravam, если я вас правильно понял, то в эту область помещаются только неинициализированные переменные.То есть если глобальная переменная инициализирована, то она помещается в стек.И так же справедливо, что если переменная локальна, но не инициализирована, то она помещается в эту область.Я Вас верно понял? Добавлено через 9 минут Всем спасибо за ответы! 0

@ZaMaZaN4iK Мой лучший друг-отладчик! 167 / 167 / 30 Регистрация: 24.06.2012 Сообщений: 662 Записей в блоге: 5
	28.04.2013, 22:32 [ТС]
	kravam, большое спасибо - теперь понял, наконец-то, как оно всё хранится. 0