Как можно оптимизировать код?

Question

[Евгений Боавский]

#include <iostream>
#include <vector>

using namespace std;

int main() {
    long n, m;

    cin >> n >> m;

    long a[n][4];
    long b[m][2];

    for(long i = 0; i < n; i++)
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];

    for(long i = 0; i < m; i++)
        cin >> b[i][0] >> b[i][1];
    

    long k =0;

    vector<bool> vec(m, true);

    for(long i = 0; i < m; i++)
    {
        for(long j = 0; j < n; j++)
        {
            if((b[i][0] >= a[j][0] &&  b[i][1] >= a[j][1]) && ( b[i][0] <= a[j][2] && b[i][1] <= a[j][3]) && vec[j])
            {
                cout << j + 1 << " ";
                vec[j] = false;
                k = 1;
                break;
            }
            k = 0;
        }
        if(k == 0)
            cout << "-1 ";
    }

    return 0;
}

Comments

[tugo]

Что хотите улучшить? Скорость выполнения, память, читабельность?

[tugo]

for (long i = 0; i < m; i++)
{
    bool k = false;

    for (long j = 0; j < n; j++)
    {
        if ((b[i][0] >= a[j][0] &&  b[i][1] >= a[j][1]) && ( b[i][0] <= a[j][2] && b[i][1] <= a[j][3]) && vec[j])
        {
            cout << j + 1 << " ";
            vec[j] = false;
            k = true;
            break;
        }
    }
    
    if (!k)
        cout << "-1 ";
}

[Евгений Боавский]

tugo, Нужна скорость. Думаю тут Динамическое программирование надо использовать. Только не знаю как его сделать

[Евгений Боавский]

tugo, tugo, 4 10
0 0 1 1
2 3 3 8
15 15 20 20
10 12 12 13
2 2
0 -1
23 18
13 12
10 13
16 16
17 17
3 5
3 5
3 3

Там вот такие данные должны быть

[Евгений Боавский]

tugo, И вот это на вывод -1 -1 -1 -1 4 3 -1 2 -1 -1

[Евгений Шатунов]

Евгений Боавский, скорость достигается профилированием на целевой архитектуре. Какая у тебя целевая архитектура?

[Евгений Боавский]

Евгений Шатунов, Мне это на олимпиаду надо, там две задачи одинаковые. На первой по тестам прошло, на второй пишет, что долго выполняется на 58 тесте

[Евгений Шатунов]

Евгений Боавский, это на мой вопрос никак не отвечает. На олимпиадах заявляются характеристики тестирующего оборудования.
Видимо, оптимизация тебе нужна не по характеристике скорости, а алгоритмическая.
Ты условие задачи и тестовый ввод/вывод не написал. В коде у тебя откровенно фраш, понимать и оптимизировать просто нечего. Да, там очень недостает unsigned чтобы все еще больше усугубить.

[tugo]

Евгений Боавский,
1 .вынесите cout за пределы двойного вложенного цикла. Накапливайте числа в массиве. После выхода из двойного цикла распечатайте этот накопленный массив.
2. Если не хватает, попробуйте перейти с cout на printf. Это может дать ускорение.
https://stackoverflow.com/questions/1736267/c-cout...
3. Замените std::vector на std::arrary. https://stackoverflow.com/questions/4424579/stdvec...

[tugo]

Евгений Боавский, пришлите ссылку на задачу.

[Евгений Шатунов]

Евгений Боавский, я так понимаю, за давностью лет вопрос утратил актуальность? Сообществу такой вопрос вряд ли окажется полезным, особенно без ответа. Может быть ты его просто уберешь?

Answer 1

[Рональд Макдональд]

Ну, раз все молчат...
for(long i
Почему лонг? Unsigned int за глаза.

Comments

[Евгений Боавский]

В тестах работает

[DanielMcRon]

Евгений Боавский, Лонг берёт больше памяти,чем uint,уже неплохая оптимизация для этого куска кода