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.
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