Задать вопрос

FaxWeb

Комментарии

  • Как найти кратчайший путь в лабиринте, двигаться в котором можно только вперед и направо?

    @FaxWeb Автор вопроса
    Wataru, точно, изменил начальное состояние для dist и q, и все тесты прошли, спасибо. Понял про массивы, ДП буду чуть позже изучать, там и узнаю всю красоту 5-мерных массивов судя по всему)
    Написано

  • Как найти кратчайший путь в лабиринте, двигаться в котором можно только вперед и направо?

    @FaxWeb Автор вопроса
    Ошибку понял, изменил dist на трехмерный массив, теперь код учитывает и направление. Но решение прошло только 70% тестов, что-то все еще не так. И вообще, использование 3d массива считается нормой для такой задачи, или лучше стараться этого избегать и писать иначе?
    Измененная функция bfs:
    int bfs(vs &g, pair<int, int> start){
    int h = g.size(), w = g[0].size();
    vector<vector<vi>> dist(h, vector<vi>(w, vi(4, INF)));
    queue<Vertex> q;

    dist[start.first][start.second][0] = 0;
    q.push({ start.first, start.second, 0 });

    while (!q.empty()){
        Vertex v = q.front();
        q.pop();

        if (g[v.y][v.x] == 'F'){
            return dist[v.y][v.x][v.dir];
        }

        for (Vertex &option : getOptions(g, v)){
            if (dist[option.y][option.x][option.dir] > dist[v.y][v.x][v.dir] + 1){
                dist[option.y][option.x][option.dir] = dist[v.y][v.x][v.dir] + 1;
                q.push(option);
            }
        }
    }

    return -1;
}
    Написано

  • Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

    @FaxWeb Автор вопроса
    Wataru, да, так все тесты прошел, что-то действительно криво

    #include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n){
        maxCapacity = n;
    }

    pair<int, ll> extractMax(){
        if (arr.size() == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {1, arr[0]};
        arr[0] = arr.back();
        arr.pop_back();
        int current = 0;
        if (arr.size() == 0) {
            res.first = -2;
            return res;
        }
        while (2*current+1 < arr.size()){
            int maxP;
            if (2*current+1 == arr.size()-1){
                maxP = 2*current+1;
            } else {
                maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            } 

            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (arr.size() == maxCapacity) return -1;

        int current = arr.size();
        arr.push_back(num);
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            } else if (res.first == -2){
                cout << 0 << " " << res.second << endl;
            } else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }

    for (int i = 0; i < heap.arr.size(); i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}
    Написано

  • Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

    @FaxWeb Автор вопроса
    Wataru, может и тесты кривые, но тестов я не знаю, загружаю свои решения сюда: https://informatics.msk.ru/mod/statements/view.php...

    А так еще заметил в условии что extractMax может и 0 выводить в качестве индекса:
    В ответ на запрос типа 1 следует вывести:
    • Если извлекать было нечего (очередь пуста), то -1.
    • Иначе, как и в предыдущей задаче – два числа: первое – индекс конечного положения элемента после его просеивания (если же удалён был
    последний элемент и просеивать осталось нечего, вывести 0)    ; второе –
    значение извлечённого элемента.

    код который раз поменял, но ничего не изменилось
    #include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n){
        maxCapacity = n;
    }

    pair<int, ll> extractMax(){
        if (arr.size() == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {1, arr[0]};
        arr[0] = arr.back();
        arr.pop_back();
        int current = 0;
        if (arr.size() == 0) return pair<int, ll> (-2, -2);
        while (2*current+1 < arr.size()){
            int maxP;
            if (2*current+1 == arr.size()-1){
                maxP = 2*current+1;
            } else {
                maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            } 

            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (arr.size() == maxCapacity) return -1;

        int current = arr.size();
        arr.push_back(num);
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            } else if (res.first == -2){
                cout << 0 << endl;
            } else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }
    for (int i = 0; i < heap.arr.size(); i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}
    Написано

  • Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

    @FaxWeb Автор вопроса
    ошибку с 1 ребенком тоже учел, но она мне правильных тестов не прибавила

    #include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct MaxHeap{
    int maxCapacity;
    vector<ll> arr;
    MaxHeap(int n){
        maxCapacity = n;
    }

    pair<int, ll> extractMax(){
        if (arr.size() == 0) return pair<int, ll>(-1, -1);

        pair<int, ll> res = {1, arr[0]};
        arr[0] = arr.back();
        arr.pop_back();
        int current = 0;
        while (2*current+1 < arr.size()){
            int maxP;
            if (2*current+1 == arr.size()-1){
                maxP = 2*current+1;
            } else {
                maxP = (arr[2*current+1] >= arr[2*current+2] ? 2*current+1 : 2*current+2);
            } 
            
            if (arr[current] < arr[maxP]){
                swap(arr[current], arr[maxP]);
                current = maxP;
                res.first = maxP+1;
            } else {
                break;
            }
        }
        return res;
    }

    int add(ll num){
        if (arr.size() == maxCapacity) return -1;

        int current = arr.size();
        arr.push_back(num);
        while (current > 0 && arr[(current-1)/2] < arr[current]){
            swap(arr[(current-1)/2], arr[current]);
            current = (current-1)/2;
        }
        return current+1;
    }
};

int main(){
    int n, m;
    cin >> n >> m;

    MaxHeap heap(n);
    for (int i = 0; i < m; i++){
        int command;
        cin >> command;
        if (command == 1){
            pair<int, ll> res = heap.extractMax();
            if (res.first == -1) {
                cout << -1 << endl;
            }
            else {
                cout << res.first << " " << res.second << endl;
            }
        } else {
            ll num;
            cin >> num;
            cout << heap.add(num) << endl;
        }
    }

    for (int i = 0; i < heap.arr.size(); i++) {
        cout << heap.arr[i] << " ";
    }

    return 0;
}
    Написано

  • Как реализовать приоритетную очередь с функциями extractMax и add, которая поддерживает одинаковые элементы?

    @FaxWeb Автор вопроса
    По поводу вектора я понял, напутал я с reserve и resize. Но если говорить об индексах, то это вы правильно подметили про случай с новым максимальным элементом, и я поменял строку с созданием пары res{0, arr[0]} на res{1, arr[0]}, теперь этот случай учтен и несколько тестов мне это прибавило, но все равно все тесты такой код не закрывает :(
    Написано