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
#33182
i_can0803 (Thành viên)
flp_102
Đã code là AC
Bài viết: 104
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, 1 tháng trước   (+0)
HNUE_D viết:
QUOTE:
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.
 
Ko rõ sai đâu nhưng phần đọc mình thấy trên diễn đàn bảo là trên SPOJ ko có seekeof mà chỉ có eof thui.Bạn xem lại nhé
 
Đã lưu IP Đã lưu IP  
 
No thing is impossible!
  Đã khóa chức năng gửi bài.
#49972
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, 6 tháng trước   (+0)
HNUE_D viết:
QUOTE:
Bài này e đã down test về và thấy đúng hết, chạy không có lỗi j


cho mình hỏi bạn down test bài này ở đâu vậy
mình muốn test thử, chả hiểu sao cứ bị lỗi SIGKILL miết phát bực
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#49976
nkkidokid (Thành viên)
nkkidokid-
Nhắm mắt code không bug
Bài viết: 140
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, 6 tháng trước   (+0)
bạn để eof(f) hoặc là seekeof nhé
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#49982
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, 6 tháng trước   (+0)
input kết thúc bằng số 0 mà, đâu có cần để eof(f) đâu bạn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#49993
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, 6 tháng trước   (+0)
thui thì post code lên lun các bạn xem giùm với, mình bị lỗi SIGKILL, dùng 2 heap min-max


Code:
#include <stdio.h>
 
#define nmax 10000009
 
typedef struct heap
{
        long val,posmin,posmax,khach;
} heap;
 
heap min[nmax*2],max[nmax*2];
long nheap;
 
int up_max(long pos)
{
    long i;
    heap tam;
    if (pos==1) return 0;
    i=pos/2;
    if (max[i].val<max[pos].val)
    {
       tam=max[i];
       max[i]=max[pos];
       max[pos]=tam;
       min[max[i].posmin].posmax=i;
       min[max[pos].posmin].posmax=pos;
       up_max(i);
    }
    return 0;
}
 
int up_min(long pos)
{
    long i;
    heap tam;
    if (pos==1) return 0;
    i=pos/2;
    if (min[i].val>min[pos].val)
    {
       tam=min[i];
       min[i]=min[pos];
       min[pos]=tam;
       max[min[i].posmax].posmin=i;
       max[min[pos].posmax].posmin=pos;
       up_min(i);
    }
    return 0;
}
 
void them(long k,long p)
{
     nheap++;
     min[nheap].khach=k;
     min[nheap].val=p;
     min[nheap].posmax=nheap;
     max[nheap].khach=k;
     max[nheap].val=p;
     max[nheap].posmin=nheap;
     up_max(nheap);
     up_min(nheap);
}
 
int down_max(long pos)
{
    long i=pos*2;
    heap tam;
    if (pos>nheap) return 0;
    if (i>nheap) return 0;
    if ((i<nheap) && (max[i].val<max[i+1].val)) i++;
    if (max[i].val>max[pos].val)
    {
       tam=max[i];
       max[i]=max[pos];
       max[pos]=tam;
       min[max[i].posmin].posmax=i;
       min[max[pos].posmin].posmax=pos;
       down_max(i);
    }
    return 0;
}
 
int down_min(long pos)
{
    long i=pos*2;
    heap tam;
    if (pos>nheap) return 0;
    if (i>nheap) return 0;
    if ((i<nheap) && (min[i].val>min[i+1].val)) i++;
    if (min[i].val<min[pos].val)
    {
       tam=min[i];
       min[i]=min[pos];
       min[pos]=tam;
       max[min[i].posmax].posmin=i;
       max[min[pos].posmax].posmin=pos;
       down_min(i);
    }
    return 0;
}
 
void pop_max()
{
     long vitri=max[1].posmin;
     max[1]=max[nheap];
     min[max[1].posmin].posmax=1;
     min[vitri]=min[nheap];
     if (vitri!=nheap) max[min[vitri].posmax].posmin=vitri;
     nheap--;
     down_max(1);
     up_min(vitri);
     down_min(vitri);
}
 
void pop_min()
{
     long vitri=min[1].posmax;
     min[1]=min[nheap];
     max[min[1].posmax].posmin=1;
     max[vitri]=max[nheap];
     if (vitri!=nheap) min[max[vitri].posmin].posmax=vitri;
     nheap--;
     down_min(1);
     up_max(vitri);
     down_max(vitri);
}
 
void xuly()
{
     long k,p,c;
     nheap=0;
     while (scanf("%d",&c)!=EOF)
     {
           if (c==0) break;  
           if (c==1)
           {
              scanf("%d%d",&k,&p);
              them(k,p);
           }
           else if (c==2)
           {
              if (!nheap) printf("0\n");
              else 
              {
                   printf("%d\n",max[1].khach);
                   pop_max();
              }  
           }
           else
           {
              if (!nheap) printf("0\n");
              else
              {
                  printf("%d\n",min[1].khach);
                  pop_min();
              }
           }
     }
}
 
int main()
{
    xuly();
    return 0;
}
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#50746
ngmq (Thành viên)
Biết code binary-indexed tree
Bài viết: 42
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)
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

Đây là code của mình, chỉ dùng 1 heap, tận dụng STL C++.


Code:
 
#include<cstdio>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<bitset>
#include<stack>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
 
typedef long long int ll;
#define INF 2023456789
#define FOR(i,a,b) for(int i = a; i < b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
 
 
struct customer{
  int k;
  int p;
};
 
bool comax(const customer &c1, const customer &c2){
  return c1.p < c2.p;
}
 
bool comin(const customer &c1, const customer &c2){
  return c1.p > c2.p;
}
 
customer e , h[82000];
int co, nh ;
int d = 0;
int l[82000];
 
int main() {
  //freopen("in.txt","r",stdin);
  //freopen("out.txt","w",stdout);
 
  while(true){
    scanf("%d",&co);
    if(co == 0) break;
    if(co == 1){
      scanf("%d%d",&e.k, &e.p);
      h[nh] = e;
      nh++;
      push_heap(&h[0],&h[nh],comax);
 
    }
    else if(co == 2){
      if(nh == 0){
        l[d++] = 0;
      }
      else {
        make_heap(&h[0],&h[nh],comax);
        l[d++] = h[0].k;
        pop_heap(&h[0],&h[nh--],comax);
      }
    }
    else if(co == 3) {
      if(nh == 0)
        l[d++] = 0;
      else {
        make_heap(&h[0],&h[nh],comin);
        l[d++] = h[0].k;
        pop_heap(&h[0],&h[nh--],comin);
      }
    }
  }
  FOR(i,0,d){
      printf("%d\n",l[i]);
    }
}
 
 
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#50773
hunterphu (Thành viên)
hunterphu+19
Nhắm mắt code không bug
Bài viết: 282
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)
Mỗi thao tác make_heap mất chi phí là klogk với k là số phần tử của heap => độ phức tạp là n*klogk
Bài này mình code từ lúc chưa học heap, bài của mình dùng BST mà ko dùng bất cứ thao tác nào để cân bằng cây
Nên việc bạn AC ở trang khác có thể là do test random
 
Đã lưu IP Đã lưu IP  
 
tren tay em nu hoa van no, pho xa pho xa ...
  Đã khóa chức năng gửi bài.
#50782
lamphanviet (Thành viên)
lamphanviet+6
Biết code binary-indexed tree
Bài viết: 20
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)
Bài này mình sử dụng set trong STL C++ .
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#50786
ngmq (Thành viên)
Biết code binary-indexed tree
Bài viết: 42
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)
Cảm ơn gợi ý của anh hunterphu mình chuyển sang dùng STL set ( BST ) thay vì heap và đã AC đúng là ở voj bị TLE do đoạn make_heap đó.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#50841
narutotq95 (Thành viên)
narutotq95+1
Biết code binary-indexed tree
Bài viết: 27
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)
Thật ra dùng Set cho tiện thôi, chứ việc tự code lại Heap vẫn là chuẩn nhất, và nhanh hơn so với Set, trừ trường hợp giá trị trong heap quá lớn, ko lưu được mảng Pos (để tìm kiếm).

Dù biết dùng Set nhưng quen tay nên lúc nào mình cũng tự code Heap
 
Đã 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