2

Есть консольная программа, работу которой очень замедляет ввод и вывод данных. Количество запросов - до 100000, в одном запросе число от -1 до 1, пробел, число от -10 в 9 степени, до 10 в 9 степени. С scanf, printf работает слишком медленно. Пытался использовать getchar, но он записывает только 1 символ.

#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

int main()
{
    int n, a, N, I, J;
    vector<int> vec;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a, &N);
        if (a == 1)
        {
            I = 0;
            J = vec.size();
            if (vec.size() != 0)
            {
                while (J - I > 0)
                {
                    if (N < vec[(I + J) / 2])
                    {
                        J = (I + J) / 2;
                    }
                    else
                    {
                        I = (I + J) / 2;
                        if (J - I <= 1)
                        {
                            I = J;
                            break;
                        }
                    }
                }
                vector<int>::iterator it = vec.begin() + J;
                vec.insert(it, N);
            }
            else vec.push_back(N);
        }
        else if (a == -1)
        {
            auto f = lower_bound(vec.begin(), vec.end(), N);
            vec.erase(f);
        }
        else
        {
            printf("%d\n", vec[vec.size() - N]);
        }
    }
}
12
  • 1
    Откуда вводятся данные? Куда выводятся? Вы вручную вводите 100000 пар scanfом? Выводите на экран 100000 строк? Вы их вообще читаете? :)
    – Harry
    28 фев 2021 в 14:11
  • @Harry данные вводатся онлайн тестером e-olymp. на экран выводится примерно 1/3 от запросов
    – Ultra_Dog
    28 фев 2021 в 14:12
  • 1
    А с чего вы решили, что дело в скорости чтения и вывода? Может, в первую очередь поискать более быстрое решение задачи? Что за задача, кстати?
    – Harry
    28 фев 2021 в 14:13
  • @Harry e-olymp.com/ru/problems/687 85% тестов проходит, 400 миллисекунд нехватает на остальные.
    – Ultra_Dog
    28 фев 2021 в 14:15
  • 400ms - уйма времени, проблема не в чтении...
    – Harry
    28 фев 2021 в 14:18

1 ответ 1

4

Оценка времени ввода/вывода

Сгенерируем вход максимального размера:

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror generate_input.cpp

#include <cstdio>

int main() {
    const int n = 100000;
    printf("%d\n", n);
    for (int i = 0; i < n; ++i) {
        switch (i % 3) {
            case 0: printf("+1 1000000000\n"); break;
            case 1: printf("0 1000000000\n"); break;
            case 2: printf("-1 1000000000\n"); break;
        }
    }
}
$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror generate_input.cpp
$ ./a.out >input
$ wc input 
 100001  200001 1366674 input
$ head input 
100000
+1 1000000000
0 1000000000
-1 1000000000
+1 1000000000
0 1000000000
-1 1000000000
+1 1000000000
0 1000000000
-1 1000000000

Затем сымитируем чтение и запись:

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror process_input.cpp

#include <cstdio>

int main() {
    int n;
    if (scanf("%d", &n) != 1) {
        return 1;
    }
    for (int i = 0; i < n; ++i) {
        int c, k;
        if (scanf("%d%d", &c, &k) != 2) {
            return 1;
        }
        if (c == 0) {
            printf("%d\n", k);
        }
    }
}
$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror process_input.cpp
$ ./a.out <input >output
$ wc output
33333  33333 366663 output
$ head output
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

Прогоним обработку несколько раз:

$ time ./a.out <input >output

real  0m0.022s
user  0m0.016s
sys   0m0.004s

$ time ./a.out <input >output

real  0m0.023s
user  0m0.020s
sys   0m0.000s

$ time ./a.out <input >output

real  0m0.020s
user  0m0.012s
sys   0m0.004s

Худшее время 23ms. Проблема в алгоритме, не в чтении или записи.

Как можно решить задачу быстро

Нужно сжать вход и применить дерево отрезков.

Вход cчитывается в память. Значения индексов k_i для команд +1/-1 сортируются по убыванию. В дальнейшем решении будут участвовать не значения k_i а их номера в порядке убывания. Номера эти по условию задачи не превосходят 100000.

Для номеров создаётся и обновляется дерево отрезков размера не более 2 * 2^17 (это ближайшая степень двойки большая 2 * 100000). Дерево поддерживает вставку элемента, его удаление и поиск по порядковому номеру за логарифм от размера.

Решение ниже проходит все тесты e-olymp:687. Худшее время 31ms.

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror solution.cpp

#include <algorithm>
#include <cstdio>
#include <vector>

struct Command {
    int c;
    int k;
};

typedef std::vector<Command> Commands;

void read(Commands &commands) {
    int n;
    if (scanf("%d", &n) != 1) {
        return;
    }
    for (int i = 0; i < n; ++i) {
        int c, k;
        if (scanf("%d%d", &c, &k) != 2) {
            return;
        }
        commands.push_back({c, k});
    }
}

typedef std::vector<int> Index;

void reindex(Commands &commands, Index &index) {
    std::vector<Command *> refs;

    for (Command &c : commands) {
        if (c.c != 0) {
            refs.push_back(&c);
        }
    }
    // reversed sort
    std::sort(
        refs.begin(),
        refs.end(),
        [](const Command *c1, const Command *c2) -> bool { return c1->k > c2->k; }
    );
    int i = -1;
    if (refs.size() != 0) {
        int k = refs.front()->k - 1;
        for (Command *c : refs) {
            if (c->k != k) {
                ++i;
                index.push_back(c->k);
                k = c->k;
            }
            c->k = i;
        }
        ++i;
    }
}

class Tree {
public:
    Tree(int n) : size(data_size(n)), data(2 * size, 0) {
    }

    void add(int i, int v) {
        int j = size + i;
        while (j != 0) {
            data[j] += v;
            j /= 2;
        }
    }

    int get_stat(int k) const {
        int j = 1;
        while (j < size) {
            j *= 2;
            if (data[j] <= k) {
                k -= data[j];
                ++j;
            }
        }
        return j - size;
    }

private:
    int size;
    std::vector<int> data;

    static int data_size(int i) {
        int p = 1;
        while (p < i) {
            p *= 2;
        }
        return p;
    }
};

int main() {
    Commands commands;
    read(commands);

    Index index;
    reindex(commands, index);

    Tree tree(index.size());
    for (const Command &c : commands) {
        if (c.c == 0) {
            printf("%d\n", index[tree.get_stat(c.k - 1)]);
        } else {
            tree.add(c.k, c.c);
        }
    }
    return 0;
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.