Editorial for Hàng đợi có độ ưu tiên


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=15010;
var h,re:array[1..maxn] of longint;
    n,dem:longint;

procedure update(x:longint);
var cha,con:longint;
begin
     inc(n);
     con:=n; cha:=con shr 1;
     while (cha>0) and (h[cha]<x) do
     begin
          h[con]:=h[cha];
          con:=cha;
          cha:=con shr 1;
     end;
     h[con]:=x;
end;

function pop(val:longint):longint;
var cha,con,x:longint;
begin
     while (h[1]=val) and (n>0) do
     begin
          pop:=h[1];
          x:=h[n];
          dec(n);
          cha:=1; con:=2;
          while con<=n do
          begin
               if (con<n) and (h[con+1]>h[con]) then inc(con);
               if x>=h[con] then break;
               h[cha]:=h[con];
               cha:=con;
               con:=cha shl 1;
          end;
          h[cha]:=x;
     end;
end;

procedure pr;
var i,x:longint; c:char;
begin
     while not eof do
     begin
          read(c);
          if c='+' then
          begin
               read(x);
               if n<15000 then update(x);
          end
          else x:=pop(h[1]);
          readln;
     end;
     repeat
           inc(dem);
           re[dem]:=pop(h[1]);
     until n=0;
     writeln(dem);
     for i:=1 to dem do writeln(re[i]);
end;

begin
     pr;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N

char s[100000];

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    priority_queue<int> qu;
    while(gets(s) != NULL) {
        if( s[0] == '-' ) {
            if(!qu.empty()) {
                int mx = qu.top();
                while(!qu.empty() && qu.top() == mx) qu.pop();
            }
        } else if(qu.size() < 15000) {
            qu.push(atoi(s+1));
        }
    }
    vi res;
    int prev = INT_MAX;
    for(;!qu.empty(); qu.pop()) {
        if(qu.top() != prev)
        res.pb(prev = qu.top());
    }
    printf("%d\n", res.size());
    tr(res,it) printf("%d\n", *it);
    return 0;
}

Code mẫu của ladpro98

#include <iostream>

using namespace std;

const int N = 2e5;

struct Heap {
    int a[N];
    int size;

    Heap() { size = 0; }
    int top() { return a[1]; }
    void pop() {
        a[1] = a[size];
        a[size--] = 0;
        down(1);
    }
    void push(int v) {
        a[++size] = v;
        up(size);
    }

    void up(int v) {
        if (v == 1) return;
        int p = v / 2;
        if (a[p] < a[v]) {
            swap(a[p], a[v]);
            up(p);
        }
    }

    void down(int u) {
        if (u * 2 > size) return;
        int v = u * 2;
        if (a[v + 1] > a[v])
            v += 1;
        if (a[u] < a[v]) {
            swap(a[u], a[v]);
            down(v);
        }
    }
} heap;

int ans[N];

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    char cmd;
    while (cin >> cmd) {
        if (cmd == '+') {
            int v; cin >> v;
            if (heap.size < 15000) heap.push(v);
        } else {
            int v = heap.top();
            while (heap.size && heap.top() == v) heap.pop();
        }
    }

    int n = 0;
    for (int v = -1; heap.size; heap.pop()) {
        if (heap.top() != v)
            ans[++n] = (v = heap.top());
    }

    cout << n << '\n';
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << '\n';
    return 0;
}

Code mẫu của RR

{$MODE OBJFPC}
var
  i,cnt,save,tmp,hsize,u:longint;
  a,h:array[1..30111] of longint;
  c:char;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure down(i:longint);
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and (h[j+1]>h[j]) then inc(j);
          if h[j]>h[i] then
            begin
              swap(h[i],h[j]);
              i:=j; j:=i shl 1;
            end
          else exit;
        end;
    end;

procedure up(i:longint);
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and (h[i]>h[j]) do
        begin
          swap(h[i],h[j]);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u:longint);
    begin
      inc(hsize);
      h[hsize]:=u;
      up(hsize);
    end;

function pop:longint;
    begin
      result:=h[1];
      swap(h[1],h[hsize]);
      dec(hsize);
      down(1);
    end;

begin
  while not eof do
    begin
      read(c);
      if c='+' then
        begin
          readln(u);
          if hsize<15000 then
              push(u);
        end
      else
        begin
          readln;
          if hsize>0 then
            begin
              u:=h[1];
              while (hsize>0) and (h[1]=u) do
                  tmp:=pop;
            end;
        end;
    end;

  save:=1000111000;

  while hsize>0 do
    begin
      u:=pop;
      if u<>save then
        begin
          inc(cnt);
          a[cnt]:=u;
          save:=u;
        end;
    end;

  writeln(cnt);
  for i:=1 to cnt do
    writeln(a[i]);
end.

Code mẫu của hieult

#include<iostream>
//#include<conio.h>
#include<algorithm>
#include<vector>
#include<string.h>

using namespace std;

vector<long> a;

int main()
{
 string st;
 char ch;
 long x,i,t=0;
 //freopen("qbheap.inp","r",stdin);
 while((cin>>ch)>0)
 {
 if (ch == '+')
   {
    cin>>x;
    if (a.size()<15000)
    {
      a.push_back(x);
      push_heap(a.begin(),a.end());
    }
   }
  else 
    if (a.size() > 0)
    {
     x = a[0];
     while (x==a[0]&&a.size()>0)
      {
        pop_heap(a.begin(),a.end());
        a.pop_back();
      }   
    }
  }
 sort_heap(a.begin(),a.end());
 for (i=a.size()-1;i>=1;i--)
  if (a[i] != a[i-1])
    {
    t++;
    }   
 printf("%ld\n",t+1); 
 for (i=a.size()-1;i>=1;i--)
  if (a[i] != a[i-1])
    {
    printf("%ld\n",a[i]);
    }
 printf("%ld",a[0]);         
//getch();
}

Code mẫu của ll931110

Program QBHEAP;
        Const
                input  = '';
                output = '';
        Var
                heap,a: array[0..15000] of longint;
                 nHeap: integer;

Procedure update(v: longint);
          Var
                parent,child: integer;
          Begin
                inc(nHeap);
                heap[nHeap]:= v;

                child:= nHeap;
                parent:= child div 2;

                While (parent > 0) and (heap[parent] < v) do
                      Begin
                                heap[child]:= heap[parent];
                                child:= parent;
                                parent:= child div 2;
                      End;

                heap[child]:= v;
          End;

Function get: longint;
         Begin
                get:= heap[1];
         End;

Procedure pop;
          Var
                r,c,v,t: longint;
          Begin
                heap[1]:= heap[nHeap];
                dec(nHeap);

                r:= 1;
                v:= heap[r];

                While r * 2 <= nHeap do
                      Begin
                        c:= r * 2;
                        If (c < nHeap) and (heap[c + 1] > heap[c]) then inc(c);

                        If v >= heap[c] then break;
                        heap[r]:= heap[c];
                        r:= c;
                      End;

                heap[r]:= v;
          End;

Procedure solve;
          Var
                f: text;
                v: longint;
               ch: char;
          Begin
                nHeap:= 0;

                Assign(f, input);
                        Reset(f);

                While not eof(f) do
                      Begin
                                Read(f, ch);
                                If ch = '+' then
                                        Begin
                                                Readln(f, v);
                                                If nHeap < 15000 then update(v);
                                        End
                           else if ch = '-' then
                                        Begin
                                                v:= get;
                                                While (v = get) and (nHeap > 0) do pop;
                                                Readln(f);
                                        End;
                      End;

                Close(f);
          End;

Procedure heapsort;
          Var
                    f: text;
                i,num: integer;
          Begin
                Assign(f, output);
                        Rewrite(f);

                num:= 0;
                a[0]:= -1;

                For i:= nHeap downto 1 do
                        Begin
                                If a[num] <> get then
                                        Begin
                                                inc(num);
                                                a[num]:= get;
                                        End;
                                pop;
                        End;

                Writeln(f, num);
                For i:= 1 to num do writeln(f, a[i]);

                Close(f);
          End;

Begin
        solve;
        heapsort;
End.

Code mẫu của khuc_tuan

#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;

multiset<int> se;
int a[15000], na;

int main() {
    char s[100];
    while(gets(s)) {
        if(s[0]=='-') {
            if(se.size()>0) {
                multiset<int> :: iterator i = se.end();
                --i;
                se.erase( *i );
            }
        } else {
            int x;
            sscanf(s+1, "%d", &x);
            if(se.size()<15000) se.insert(x);
        }
    }

    for(set<int> :: reverse_iterator p = se.rbegin(); p!=se.rend(); ++p) 
        a[na++] = *p;
    int n = na==0?0:1;
    for(int i=1;i<na;++i) if(a[i]!=a[i-1]) a[n++] = a[i];
    printf("%d\n", n);
    for(int i=0;i<n;++i) printf("%d\n", a[i]);
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.