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
#18945
tsgvhn (Thành viên)
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
MSE07B 11 năm, 3 tháng trước   (+0)
Các pro xem code giúp em với. Em sub lên nó báo WA hoài

Thx anh. Em AC rồi.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#18950
khuc_tuan (Admin)
khuc_tuan+137
Admin
Bài viết: 1472
graph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: MSE07B 11 năm, 3 tháng trước   (+0)
Lúc popmin / popmax bạn thay đổi vị trí phần tử trong heap nhưng chưa cập nhật mảng Pmin / Pmax
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#25351
oh!good (Thành viên)
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 10 năm, 8 tháng trước   (+0)
Code:
 
{$mode objfpc}
program sdf;
const
fo='';
fi='';
type
hs=record
x,y:integer;
end;
var
f,g:text;
a,b:array[0..1000001]of hs;
c,d:array[0..1000001]of integer;
n,t1,t2:integer;
procedure swap(var x,y:hs);
 var t:hs;
 begin
 t:=x;
 x:=y;
 y:=t;
 end;
procedure swap1(var x,y:integer);
 var t:integer;
 begin
 t:=x;
 x:=y;
 y:=t;
 end;
procedure upheap1(i:integer);
  begin
  if (i<=1)or(a[i].y<=a[i div 2].y) then exit;
   swap1(c[a[i].x],c[a[i div 2].x] );
   swap(a[i],a[i div 2]);
   upheap1(i div 2);
  end;
procedure upheap2(i:integer);
   begin
  if (i<=1)or(b[i].y>=b[i div 2].y) then exit;
  swap1(d[b[i].x],d[b[i div 2].x]);
  swap(b[i],b[i div 2]);
  upheap2(i div 2);
  end;
procedure downheap1(i,k:integer);
var
 t:integer;
   begin
   t:=i*2;
   if (t>k)or((a[i].y>=a[t].y)and(a[i].y>=a[t+1].y)) then exit;
   if a[t].y<a[t+1].y then inc(t);
   swap1(c[a[i].x],c[a[t].x]);
   swap(a[i],a[t]);
   downheap1(t,k);
   end;
procedure downheap2(i,k:integer);
var
 t:integer;
   begin
   t:=i*2;
   if (t>k)or((b[i].y<=b[t].y)and(b[i].y<=b[t+1].y)) then exit;
   if b[t].y>b[t+1].y then inc(t);
   swap1(d[b[i].x],d[b[t].x]);
   swap(b[i],b[t]);
   downheap1(t,k);
   end;
procedure push1(x:hs);
  begin
  inc(t1);
  a[t1]:=x;
  upheap1(t1);
  end;
procedure push2(x:hs);
  begin
  inc(t2);
  b[t2]:=x;
  upheap2(t2);
  end;
function pop1(i:integer):integer;
   begin
   pop1:=a[i].x;
   a[i]:=a[t1];
   c[a[i].x]:=c[a[t1].x];
   dec(t1);
   upheap1(i);
   downheap1(i,t1);
   end;
function pop2(i:integer):integer;
   begin
   pop2:=b[i].x;
   d[b[i].x]:=d[b[t2].x];
   b[i]:=b[t2];
   dec(t2);
   upheap2(i);
   downheap2(i,t2);
   end;
procedure init;
  begin
  t1:=0;
  t2:=0;
  end;
procedure openf;
  begin
  assign(f,fo);
  reset(f);
  assign(g,fi);
  rewrite(g);
  end;
procedure nhap;
  var i,k,k1,k2,n:integer;
  cd:hs;
begin
 repeat
 read(f,k);
 case k of
 1:
   begin
   with cd do
   begin
   readln(f,x,y);
   d[x]:=t1+1;
   c[x]:=t2+1;
   end;
   push1(cd);
   push2(cd);
   end;
 2:
  begin
  readln(f);
  if t1=0 then writeln(g,'0')
  else
  begin
  n:=d[a[1].x];
  writeln(g,pop1(1));
  pop2(n);
  end;
  end;
 3:
  begin
  readln(f);
  if t2=0 then writeln(g,'0')
  else
   begin
   n:=c[b[1].x];
   writeln(g,pop2(1));
   pop1(n);
   end;
  end;
  end;
 until k=0;
end;
procedure closef;
 begin
 close(f);
 close(g);
 end;
begin
openf;
init;
nhap;
closef;
end.
cho hoi tai sao chuong trinh nay lai wa?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#25358
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
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 10 năm, 8 tháng trước   (+0)
đọc code khó lắm *_*
tốt nhất là nên hỏi Chúa ^^
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#25612
ledotan (Khách)
Đã biết code đệ quy
Bài viết: 10
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 10 năm, 7 tháng trước   (+0)
Cậu nói thuật toán ra đi.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#25670
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
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 10 năm, 7 tháng trước   (+0)
@Oh!Good: Câu hỏi tại sao nó WA hơi bị ngớ ngẩn, vì nó sai nên nó WA chứ sao
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#25675
chulun (Thành viên)
canhteo+10
Không code nữa rồi
Bài viết: 605
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 10 năm, 7 tháng trước   (+0)
sonpascal93 viết:
QUOTE:
@Oh!Good: Câu hỏi tại sao nó WA hơi bị ngớ ngẩn, vì nó sai nên nó WA chứ sao :))

Anh đoán bạn ấy còn chưa đọc đề đâu
 
Đã lưu IP Đã lưu IP  
 
Wish you always love and be loved!

****************

  Đã khóa chức năng gửi bài.
#25728
sonpascal93 (Thành viên)
sonpascal93-
Nhắm mắt code không bug
Bài viết: 313
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 10 năm, 7 tháng trước   (+0)
@canhteo: ai bảo em chưa đọc đề, bài này em làm rồi mà :-??
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#25861
chulun (Thành viên)
canhteo+10
Không code nữa rồi
Bài viết: 605
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 10 năm, 7 tháng trước   (+0)
anh nói ledotan
 
Đã lưu IP Đã lưu IP  
 
Wish you always love and be loved!

****************

  Đã khóa chức năng gửi bài.
#32794
HNUE_D (Thành viên)
mrcode-
Đã code là AC
Bài viết: 81
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 10 năm, 2 tháng trước   (+0)
Bài này e đã down test về và thấy đúng hết, chạy không có lỗi j nhưng khi nộp bài bị NZEC suốt mà không hiểu tại sao (từng cho là do mảng quá lớn nên bị lỗi này nhưng khi chỉnh maxn, maxnum xuống còn vài trăm thì vẫn bị vậy). Ai xem giúp e với.
Tư tưởng vẫn là dùng 2 heap.
(maxn và maxnum mọi người đừng để ý, đó là sau khi e đã thử giảm maxn và maxnum để xem có phải tại kích thước mangr lớn quá nên bị NZEC không.)
Code:
 
const
  fi='';//'b.in';
  fo='';//'b1.out';
  maxn = 445;
  maxnum = 500;
type
  re = record
    gt, p, pos1, pos2: longint;
  end;
var
//  pos1, pos2: array[0..maxn] of longint;
  sl, nheapmin, nheapmax: longint;
  f, f1: text;
  heapmin, heapmax: array[0..maxnum] of longint;
  d: array[0..maxn] of re;
procedure open;
begin
  assign(f, fi);
  reset(f);
  assign(F1, fo);
  rewrite(f1);
end;
 
procedure closefile;
begin
  close(F1);
  close(f);
end;
 
procedure push(sl:longint);
var
  child, parent: longint;
begin
 
  inc(nheapmax);
  child:=nheapmax;
  while child div 2 > 0 do
    begin
      parent:=child div 2;
      if d[heapmax[parent]].p > d[sl].p then break;
      heapmax[child]:=heapmax[parent];
      d[heapmax[child]].pos2:=child;
      child:=parent;
    end;
  heapmax[child]:=sl;
  d[sl].pos2:=child;
  inc(nheapmin);
  child:=nheapmin;
  while child div 2 > 0 do
    begin
      parent:= child div 2;
      if d[heapmin[parent]].p < d[sl].p then break;
      heapmin[child]:=heapmin[parent];
      d[heapmin[child]].pos1:=child;
      child:=parent;
    end;
  heapmin[child]:=sl;
  d[sl].pos1:=child;
end;
 
procedure solve2;
var
  num, r, c, v: longint;
begin
  num:=heapmax[1];
  writeln(f1,d[num].gt);
  r:=1;
  v:=heapmax[nheapmax];
  dec(nheapmax);
  while r*2 <= nheapmax do
    begin
      c:=r*2;
      if (c < nheapmax) and (d[heapmax[c+1]].p > d[heapmax[c]].p) then inc(c);
      if d[heapmax[c]].p <= d[v].p then break;
      heapmax[r]:=heapmax[c];
      d[heapmax[r]].pos2:=r;
      r:=c;
    end;
  heapmax[r]:=v;
  d[v].pos2:=r;
  r:=d[num].pos1;
  if r = nheapmin then dec(nheapmin)
  else
    begin
      v:=heapmin[nheapmin];
      dec(nheapmin);
      while r div 2 > 0 do
        begin
          c:=r div 2;
          if d[heapmin[c]].p < d[v].p then break;
          heapmin[r]:=heapmin[c];
          d[heapmin[r]].pos1:=r;
          r:=c;
        end;
      heapmin[r]:=v;
      d[v].pos1:=r;
    end;
end;
 
procedure solve3;
var
  num, r, v, c: longint;
begin
  num:=heapmin[1];
  writeln(f1,d[num].gt);
  r:=1;
  v:=heapmin[nheapmin];
  dec(nheapmin);
  while r * 2 <=nheapmin do
    begin
      c:=r*2;
      if (c < nheapmin) and (d[heapmin[c+1]].p < d[heapmin[c]].p) then inc(c);
      if d[heapmin[c]].p >= d[v].p then break;
      heapmin[r]:=heapmin[c];
      d[heapmin[r]].pos1:=r;
      r:=c;
    end;
  heapmin[r]:=v;
  d[v].pos1:=r;
  r:=d[num].pos2;
  if r = nheapmax then dec(nheapmax)
  else
    begin
      v:=heapmax[nheapmax];
      dec(nheapmax);
      while r div 2 > 0 do
        begin
          c:= r div 2;
          if d[heapmax[c]].p > d[v].p then break;
          heapmax[r]:=heapmax[c];
          d[heapmax[r]].pos2:=r;
          r:=c;
        end;
      heapmax[r]:=v;
      d[v].pos2:=r;
    end;
end;
 
procedure solve;
var
  num, k, p1: longint;
 
begin
  sl:=0;
 
  while not seekeof(f) do
    begin
      read(f, num);
      if num = 1 then
        begin
          inc(sl);
          read(f, k, p1);
          d[sl].gt:=k;
          d[sl].p:=p1;
          push(sl);
 
        end;
      if num = 2 then solve2;
      if num = 3 then solve3;
    end;
 
end;
 
 
begin
  open;
  solve;
  closefile;
end.
 
 
Đã lưu IP Đã lưu IP  
  Đã 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