Разный output на разных компиляторах

@kiberqqq · Регистрация: 31.08.2015

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

Программа при входных данных:
9
1 10
1 5
1 4
1 8
1 8
3 4
2 8
2 4
3 3

Выдаёт разный результат на компиляторах Visual Studio Professional 2017 Версия 15.9.0 и g++ GNU C++ 4.9.2
Верный результат это 8 10, а на втором компиляторе выдаёт 10 10
С чем это связано? Мне кажется, что это связано с бинарным поиском, привожу код программы

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
#include <iostream>
#include <vector>
#include <set>
 
using namespace std;
 
long int binSearch(const vector <long long int> &a, const long long int &key)
{
    long int l = 0, r = a.size() - 1;
 
    while (l < r)
    {
        long int m = (l + r) / 2;
 
        if (key > a[m])
            l = m + 1;
        else if (key < a[m])
            r = m - 1;
        else
            return m;
    }
}
 
void updateTree(long int n, long int *t, long int pos, bool type)//TRUE - add 1, FALSE - sub 1
{
    pos += n;
 
    if (type) t[pos]++;
    else t[pos]--;
 
    while (pos > 1)
    {
        pos /= 2;
 
        if (type) t[pos]++;
        else t[pos]--;
    }
}
 
long int findKth(long int *t, long int num, long int l, long int r, long int k)
{
    if (l == r) return l;
 
    long int m = (l + r) / 2;
 
    if (t[2 * num] >= k)
        return findKth(t, 2 * num, l, m, k);
    else
        return findKth(t, 2 * num + 1, m + 1, r, k - t[num * 2]);
}
 
int main()
{
    long int m, n, *t, i;
 
    long long int *req;
 
    set <long long int> s;
 
    vector <long long int> uniqVec, kth;
 
    cin >> m;
    m *= 2;
 
    req = new long long int[m];
    for (i = 0; i < m; i += 2)
    {
        cin >> req[i] >> req[i + 1];
        if (req[i] == 1) s.insert(req[i + 1]);
    }
 
    uniqVec.assign(s.begin(), s.end());
 
    n = uniqVec.size();
 
    t = new long int[4 * n]();
 
    for (i = 0; i < m; i += 2)
    {
        if (req[i] == 1)
            updateTree(n, t, binSearch(uniqVec, req[i + 1]), true);
        else if (req[i] == 2)
            updateTree(n, t, binSearch(uniqVec, req[i + 1]), false);
        else
            kth.push_back(uniqVec[findKth(t, 1, 0, n - 1, req[i + 1])]);
    }
 
    for (i = 0; i < kth.size(); i++)
        cout << kth[i] << " ";
    cout << endl;
 
    delete[] req;
    delete[] t;
    return 0;
}

@Ygg · 29.05.2019, 12:38

Возможно, что проблема связана с размерами типов (long и long long).
Попробуйте вывести в консоль их sizeof. Для большей переносимости между компиляторами правильнее, наверное, использовать типы int32_t и int64_t.
Хотя, по коду не видно явных конфликтов и преобразований...

@COKPOWEHEU · 29.05.2019, 12:42

g++ ругается на 22 строку. Если условие while ложно и цикл завершится - что вернет функция?

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
$ g++ main.c -Wall -Wextra -Wpedantic
main.c: In function ‘int main()’:
main.c:88:19: warning: comparison of integer expressions of different signedness: ‘long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
     for (i = 0; i < kth.size(); i++)
                 ~~^~~~~~~~~~~~
main.c: In function ‘long int binSearch(const std::vector<long long int>&, const long long int&)’:
main.c:22:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
$ ./a.out 
9
1 10
1 5
1 4
1 8
1 8
3 4
2 8
2 4
3 3
#результат
8 10

@Ygg · 29.05.2019, 12:46

Ещё может в этом цикле дело? m - нечётное.

C++
1
2
3
4
5
6
    req = new long long int[m];
    for (i = 0; i < m; i += 2)
    {
        cin >> req[i] >> req[i + 1];
        if (req[i] == 1) s.insert(req[i + 1]);
    }

@oleg-m1973 · 29.05.2019, 12:47

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

main.c: In function ‘long int binSearch(const std::vector<long long int>&, const long long int&)’:

У binSearch return нет в конце. Что он возвращает если условие цикла while (l < r) не выполняется?

@COKPOWEHEU · 29.05.2019, 15:18

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

g++ ругается на 22 строку. Если условие while ложно и цикл завершится - что вернет функция?

Кстати, на вашем наборе данных такая ситуация возникает 3 раза.
А если в коде есть UB, различное поведение компиляторов не удивляет

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Ygg 2734 / 888 / 331 Регистрация: 10.02.2018 Сообщений: 2,099
	29.05.2019, 12:38
	Возможно, что проблема связана с размерами типов (long и long long). Попробуйте вывести в консоль их sizeof. Для большей переносимости между компиляторами правильнее, наверное, использовать типы int32_t и int64_t. Хотя, по коду не видно явных конфликтов и преобразований... 0

Разный output на разных компиляторах

Решение