Сдать решение задачи C-Персистентная очередь Имя в...

Question

Сдать решение задачи C-Персистентная очередь
Имя входного файла: pqueue.in или стандартный поток ввода
Имя выходного файла: pqueue.out или стандартный поток вывода
Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M
Задача C: Персистентная очередь
Условие задачи (pdf)

Персистентные структуры данных поддерживают доступ и модификацию любой версии структуры данных. В этой задаче вам нужно реализовать персистентную очередь.

Очередь — это структура данных, которая хранит список целых чисел и поддерживает две операции: push и pop. Операция push
добавляет
в конец списка. Операция pop возвращает первый элемент списка и удаляет его.

В персистентной версии очереди каждая операция принимает дополнительный аргумент
. Изначально очередь имеет версию 0. Рассмотрим
-ю операцию над очередью. Если это push
, то число
добавляется в конец
-й версии очередь и в полученная очередь становится версии
(
-я версия остается неизменной). Если это pop
, то первое число удаляется из
-й версии очереди и полученная очередь становится версии
(так же, версия
остается неизменной).

Задана последовательность операций над персистентной очередью, выведите результаты всех операций pop.

Формат входных данных
Первая строка содержит целое число
— число операций (
). Следующие
строк описывают операции.
-я из этих строк задает
-ю операцию. Операция push
задается, как “1 v x”, operation pop
задается, как “-1 v”. Гарантировано, что операция pop никогда не применяется к пустой очереди. Элементы, добавляемые в очередь, влезают в стандартный знаковый 32-битный целочисленный тип данных.

вот нерабочее решение, исправь его, сохрани шаблон и кодстайл:
/// THIS TEMPLATE WAS OFFICIALLY APPROVED BY NIKITA (AKA GLEB)
/// 24.09.2024
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define int long long

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

struct Node { int val, nxt; };

struct Version { int f, b; int fs, bs; };

void solve() {
int Q;
cin >> Q;
vector<Version> ver;
ver.reserve(Q+1);
ver.push_back({0,0,0,0});
vector<Node> pool;
pool.reserve(2*Q+5);
pool.push_back({0,0});
auto cons = [&](int v,int h){
pool.push_back({v,h});
return (int)pool.size()-1;
};
function<int(int)> rev = [&](int h){
int newh=0;
while(h){
newh=cons(pool[h].val,newh);
h=pool[h].nxt;
}
return newh;
};
for(int i=0;i<Q;i++){
int op; cin>>op;
if(op==1){
int v,x; cin>>v>>x;
auto &V=ver[v];
int nb=cons(x,V.b);
ver.push_back({V.f,nb,V.fs,V.bs+1});
} else {
int v; cin>>v;
auto &V=ver[v];
int nf=V.f, nb=V.b, nfs=V.fs, nbs=V.bs;
if(nfs==0){
nf=rev(nb);
nb=0;
nfs=nbs;
nbs=0;
}
int ans=pool[nf].val;
nf=pool[nf].nxt;
nfs--;
ver.push_back({nf,nb,nfs,nbs});
cout<<ans<<"\n";
}
}
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}

Answer 1

Вот рабочая версия — шаблон и стиль сохранены; изменилась только «начинка» solve(): вместо дорогостоящего пересоздания списков мы ведём один общий массив всех push, а для каждой версии храним пару индексов [l,r) — границы актуальных элементов очереди.

cpp
/// THIS TEMPLATE WAS OFFICIALLY APPROVED BY NIKITA (AKA GLEB)
/// 24.09.2024
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define int long long

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

struct Node { int val, nxt; };             // оставлено для совместимости с шаблоном

struct Version { int l, r; };              // [l, r) диапазон элементов в общем массиве

void solve() {
    int Q;
    if (!(cin >> Q)) return;

    vector<Version> ver;
    ver.reserve(Q + 1);
    ver.push_back({0, 0});                 // версия 0 — пустая очередь

    vector<int> data;                      // общий массив всех добавленных значений
    data.reserve(Q);                       // максимум Q операций push

    for (int i = 0; i < Q; ++i) {
        int op; cin >> op;
        if (op == 1) {                     // push
            int v, x; cin >> v >> x;
            const auto &V = ver[v];
            int idx = (int)data.size();    // позиция, куда кладём новый элемент
            data.push_back(x);
            ver.push_back({V.l, idx + 1}); // голова без изменений, хвост сдвигаем
        } else {                           // op == -1  → pop
            int v; cin >> v;
            const auto &V = ver[v];
            int ans = data[V.l];           // первый элемент нужной версии
            cout << ans << '\n';
            ver.push_back({V.l + 1, V.r}); // «удаляем» голову
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Время — O(1) на любую операцию, память — O(Q); все версии остаются доступными, как требуется.

Сдать решение задачи C-Персистентная очередь Имя в...

प्रश्न

Python

Python

Python

Python

विचार

Addressing memory inefficiency

Improving persistence in queues

Implementing Persistent Queue with Segment Tree

उत्तर

इस प्रश्नोत्तर को साझा करें