Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
MSE07B (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - MSE07B
#50849
huyoi (Thành viên)
huyoi+1
Đã biết code đệ quy
Bài viết: 18
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 9 năm, 5 tháng trước   (+0)
ngmq viết:
QUOTE:
Bài này mình đã AC trên UVA với time chạy 0.764s. Tuy nhiên cũng code đó nộp lên VOJ thì bị TLE :(

Thiết nghĩ máy chấm voj dù có chậm cũng không thể chênh lệch tới gần 2s được ( time limit bài này trên voj là 3s ) =((

Bạn nào bị TLE thì có thể nộp thử ở đây : http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=291&page=show_problem&problem=1832



cám ơn bạn nhé, mình đã sub thử trang đó và accept cái bụp với time 0.088s
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69026
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 8 năm, 1 tháng trước   (+0)
Bài này mình làm như sau không biết sai chỗ nào mà nộp lên bị WA:
Code:
 
- Sử dụng 1 heapmin và 1 heapmax.
- Với yêu cầu 1: thực hiện updatemin và updatemax (cập nhập lại heapmin và heapmax).
- Với yêu cầu 2: 
  + Mình gán xr:=popmax; (thằng có độ ưu tiên cao nhất).
  + Xuất nó ra.
  + Gán lại độ ưu tiên d[xr]:=+oo;
  + Updatemin(xr); (cập nhập lại vị trí của nó trong heapmin, nghĩa là bây giờ xr là phần tử có độ ưu tiên lớn nhất trong heapmin).
  + Giảm số lượng phần tử của heapmin đi 1 (loại xr ra khỏi heapmin).
  + Gán posmin[xr]:=0; (xr không còn xuất hiện trong heapmin nữa).
- Với yêu cầu 3: mình làm tương tự yêu cầu 2.
Nộp lên thấy time cũng xấp xỉ với time của những người khác AC bằng PASCAL nhưng mình lại WA. Mong mọi người giúp đỡ!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69119
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 8 năm, 1 tháng trước   (+0)
Ai AC rồi giúp mình với!
Đây là code:
Code:
- ntemax, ntemin là số lượng phần tử của heapmax,heapmin
Code:
 
PROGRAM Double_Heap;
Const   MaxN=1000*1000;
        oo=1000*1000*1000;
Var     heapmax,heapmin,posmax,posmin,d:array[0..maxn+1] of longint;
        ntemax,ntemin:longint;
 
Procedure updatemin(i:longint);
Var     cha,con:longint;
Begin
        con:=posmin[i];
        if con=0 then
        begin
                inc(ntemin);
                con:=ntemin;
        end;
        Repeat
                cha:=con div 2;
                if (cha=0) or (d[heapmin[cha]]<=d[i]) then break;
                heapmin[con]:=heapmin[cha];
                posmin[heapmin[con]]:=con;
                con:=cha;
        Until false;
        heapmin[con]:=i;
        posmin[i]:=con;
End;
 
Function popmin:longint;
Var     cha,con,i:longint;
Begin
        popmin:=heapmin[1];
        posmin[heapmin[1]]:=0;
        i:=heapmin[ntemin];
        dec(ntemin);
        cha:=1;
        Repeat
                con:=cha*2;
                if (con<ntemin) and (d[heapmin[con+1]]<d[heapmin[con]]) then inc(con);
                if (con>ntemin) or (d[heapmin[con]]>=d[i]) then break;
                heapmin[cha]:=heapmin[con];
                posmin[heapmin[cha]]:=cha;
                cha:=con;
        Until false;
        heapmin[cha]:=i;
        posmin[i]:=cha;
End;
 
Procedure updatemax(i:longint);
Var     cha,con:longint;
Begin
        con:=posmax[i];
        if con=0 then
        begin
                inc(ntemax);
                con:=ntemax;
        end;
        Repeat
                cha:=con div 2;
                if (cha=0) or (d[heapmax[cha]]>=d[i]) then break;
                heapmax[con]:=heapmax[cha];
                posmax[heapmax[con]]:=con;
                con:=cha;
        Until false;
        heapmax[con]:=i;
        posmax[i]:=con;
End;
 
Function popmax:longint;
Var     cha,con,i:longint;
Begin
        popmax:=heapmax[1];
        posmax[heapmax[1]]:=0;
        i:=heapmax[ntemax];
        dec(ntemax);
        cha:=1;
        Repeat
                con:=cha*2;
                if (con<ntemax) and (d[heapmax[con+1]]>d[heapmax[con]]) then inc(con);
                if (con>ntemax) or (d[heapmax[con]]<=d[i]) then break;
                heapmax[cha]:=heapmax[con];
                posmax[heapmax[cha]]:=cha;
                cha:=con;
        Until false;
        heapmax[cha]:=i;
        posmax[i]:=cha;
End;
 
Procedure khoitao;
Var     i:longint;
Begin
        For i:=1 to maxn do
        begin
                posmax[i]:=0;
                posmin[i]:=0;
        end;
End;
 
Procedure giai;
Var     yc,i,xr,vt:longint;
Begin
        Repeat
                read(yc);
                if yc=0 then break
                else
                if yc=1 then
                begin
                        readln(i,d[i]);
                        updatemin(i);
                        updatemax(i);
                end
                else
                if yc=2 then
                begin
                        readln;
                        if ntemax=0 then writeln(0)
                        else begin
                                xr:=popmax;
                                writeln(xr);
                                //xuly
                                d[xr]:=oo;
                                updatemin(xr);
                                dec(ntemin);
                                posmin[xr]:=0;
                        end;
                end
                else
                if yc=3 then
                begin
                        readln;
                        if ntemin=0 then writeln(0)
                        else begin
                                xr:=popmin;
                                writeln(xr);
                                //xuly
                                d[xr]:=-oo;
                                updatemax(xr);
                                dec(ntemax);
                                posmax[xr]:=0;
                        end;
                end;
 
        Until yc=0;
End;
 
BEGIN
        khoitao;
        giai;
END.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69243
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 8 năm, 1 tháng trước   (+0)
Up phát nữa!
Ai AC rồi giúp với!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69247
blackstart (Thành viên)
blackstart+40
Không code nữa rồi
Bài viết: 362
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 8 năm, 1 tháng trước   (+0)
đọc code bạn mình không hiểu nên bạn tham khảo code mình nha:
Code:
 
const maxN=1000000;
var topmin,topmax:longint;
        p,cs,hmin,hmax:array[1..maxN] of longint;
        c:array[1..maxN] of boolean;
{===================================}
procedure upmin(x:longint); inline;
var i,j:longint;
begin
        i:=topmin;
        j:=i shr 1;
        while (j>0) and (p[hmin[j]]>p[x]) do
        begin
                hmin[i]:=hmin[j];
                i:=j;
                j:=i shr 1;
        end;
        hmin[i]:=x;
end;
{===================================}
procedure upmax(x:longint); inline;
var i,j:longint;
begin
        i:=topmax;
        j:=i shr 1;
        while (j>0) and (p[hmax[j]]<p[x]) do
        begin
                hmax[i]:=hmax[j];
                i:=j;
                j:=i shr 1;
        end;
        hmax[i]:=x;
end;
{===================================}
procedure push(x:longint); inline;
begin
        c[x]:=false;
        inc(topmin);
        inc(topmax);
        upmin(x);
        upmax(x);
end;
{===================================}
procedure downmin; inline;
var i,j,x:longint;
begin
        x:=hmin[topmin];
        dec(topmin);
        i:=1;
        j:=i shl 1;
        while j<=topmin do
        begin
                if (j<topmin) and (p[hmin[j]]>p[hmin[j+1]]) then inc(j);
                if p[hmin[j]]>=p[x] then break;
                hmin[i]:=hmin[j];
                i:=j;
                j:=i shl 1;
        end;
        hmin[i]:=x;
end;
{===================================}
procedure downmax; inline;
var i,j,x:longint;
begin
        x:=hmax[topmax];
        dec(topmax);
        i:=1;
        j:=i shl 1;
        while j<=topmax do
        begin
                if (j<topmax) and (p[hmax[j]]<p[hmax[j+1]]) then inc(j);
                if p[hmax[j]]<=p[x] then break;
                hmax[i]:=hmax[j];
                i:=j;
                j:=i shl 1;
        end;
        hmax[i]:=x;
end;
{===================================}
procedure getmin; inline;
var s:longint;
begin
        s:=0;
        while (topmin>0) and (c[hmin[1]]) do downmin;
        if topmin>0 then
        begin
                s:=cs[hmin[1]];
                c[hmin[1]]:=true;
                downmin;
        end;
        writeln(s);
end;
{===================================}
procedure getmax; inline;
var s:longint;
begin
        s:=0;
        while (topmax>0) and (c[hmax[1]]) do downmax;
        if topmax>0 then
        begin
                s:=cs[hmax[1]];
                c[hmax[1]]:=true;
                downmax;
        end;
        writeln(s);
end;
{===================================}
procedure enter; inline;
var r,i:longint;
begin
        topmin:=0;
        topmax:=0;
        i:=0;
        while not eof do
        begin
                read(r);
                if r=0 then exit;
                if r=1 then
                begin
                        inc(i);
                        read(cs[i],p[i]);
                        push(i);
                end;
                if r=2 then getmax;
                if r=3 then getmin;
        end;
end;
{====================================}
begin
        enter;
end.
 
 
Đã lưu IP Đã lưu IP  
 
"Nothing is impossible; impossible itself says "I m possible"..."


Là Nam Nhi gõ phím bình thiên hạ...
Thân Anh Hùng click chuột định giang sơn...
  Đã khóa chức năng gửi bài.
#69274
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 8 năm, 1 tháng trước   (+0)
@blackstart: đọc không hiểu, có thể nói thuật giải không?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69276
luv_luxury (Thành viên)
luv_luxury-
Biết code binary-indexed tree
Bài viết: 22
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 8 năm, 1 tháng trước   (+0)
@hellosirius: Nếu người i đi ra rồi thì sẽ ko được phục vụ nữa cho đến lần vào tiếp theo. nhưng những giá trị độ ưu tiên vẫn được giữ nguyên trong Heap.
Nên khi Pop ra một người i, bạn lưu tạm vào một Stack nếu người đó đang ko ở trong Hàng đợi. Sau khi tìm được kết quả thì bạn lại Push lại các giá trị đã để ở trong Stack.
Sớm AC nhé.
 
Đã lưu IP Đã lưu IP  
 
Cộng mình cho mình hết bị trừ lào
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS