Непонятный 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, большое спасибо - теперь понял, наконец-то, как оно всё хранится.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11680&d=1772460536 Одним из. . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .

@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