Изменение положения данных во входном файле на программу. cpp Неожиданное изменение вывода

Question

Это то, для чего предназначен код: https://www.codechef.com/LRNDSA04/problems/STACKS

Вот фрагмент кода:

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<int> a;
        while(n--) {
            int x; cin >> x;
            if(a.empty()) {
                a.push_back(x);
            } else {
                vector<int>::iterator it = upper_bound(a.begin(), a.end(), x);
                int pos = it - a.begin();
                if(pos == a.size()) {
                    if(a[pos] > x) {
                        a[pos] = x;
                    } else {
                        a.push_back(x);
                    }
                } else {
                    a[pos] = x;
                }
            }
        }
        cout << a.size();
        for(auto e: a) {
            cout << " " << e;
        }
        cout << "\n";

    }
    

    return 0;
}

Вход для этой программы:

2
6
3 4 5 1 1 2
8
14 5 13 19 17 10 18 12

Неожиданный вывод, который он генерирует:

3 1 1 2
3 5 10 12

Если ввод изменен на:

2
8
14 5 13 19 17 10 18 12
6
3 4 5 1 1 2

Он показывает правильный вывод:

4 5 10 12 18
3 1 1 2

Контрольный пример с 8 числами в качестве входных данных, если их положение изменено во входном файле. Затем наблюдается такое поведение.

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

Вывод не оправдан, чего мне не хватает, чтобы увидеть?

Answer 1

В этой проверке:

if(pos == a.size()) {
    if(a[pos] > x) {   // this is UB

если условие истинно, то вы индексируете недопустимую позицию a, что вызывает неопределенное поведение.

Кажется, вы хотите вместо этого сделать

if(pos != a.size()) {

. Обычный способ проверки этого условия:

if(it != a.end()) {