Russian version: "Клиенты нумеруются в порядке поступления." English version: "The clients are numbered in the the order that they arrive, i.e. the clients number is the number d in the input." I've read russian one. Have got WA 6. Than I've read english one. And have got AC. So, IMHO, english statement is more informative. :( (Russian version may mean following: only accepted clients are numbered). Both English and Russian versions were updated. Are they OK now? I have submitted 36 times and got AC. If someone is puzzled and I hope I can help you. 1.first,read the problem's hint carefully. 2.If a tomb was visited on day T then its neighbors may be dug over on day T+101.It said "visited",so if a client was buried on day T,and a client could be buried near him on day T+1....It means when a client was buried,he has no last visit,also you can think his last visit is on day -10000. 3.A tomb is dug over as soon as there is an opportunity Becareful.AS SOON AS. 4.If someone's tomb was not dug,his relatives can visit him successful. 5.Today is T,if a tomb's last visit is before t-1000,and all it's neighbor's last visit is before t-100,it will be dug at once. So sorry for my poor English. I hope these can help you. In test 5 funeral occurs at day 0. You may see from the details. My three programs are nearly the same, but I got different time. Because I'm using CPP and I'm using FStream.h. First, n<=100 is exact! Number of Clients <= 10000! The time, you can use longint to record. I use "int" in cpp as "longint" in pascal, and I've got ACed. Don't be lost in this hint: If 1000 days since the funeral passed and the tomb is not dug over then the forgetful relatives wouldn't find the tomb and wouldn't see its neighbors. Good luck. Others are quite good. And the problem is quite easy in fact. I still have a question: If the funeral was on day 1, and on day 999 the tomb was visited, can the tomb be dug on day 1002? If on time 1, the client was buried. And on time 1001, he was visited. So if there was no more visit, this tomb cannot be dug over before time 2002. And at the same time, after time 1001, someone wanted to visit the tomb, he wouldn't find the place so the visit would effect nothing. Am I right? client #2 was visited 3 times, on 500, 1236, 2032. so the client came on time 2033 had no place to bury. and also the client came on time 300, 1001, 1003. so the answer is 4. which point did i sill misunderstand, please? > client #2 was visited 3 times, on 500, 1236, 2032. so the client > came on time 2033 had no place to bury. No, at 2004 all tombs exept the one, where client 2 rests, are dug over (empty). At 2032 relatives of clint 2 saw three empty neighbouring tombs. > and also the client came on time 300, 1001, 1003. that is true, 3 clients altogether In a hint 6 instead of "since the funeral" in should be "since the last visit" Hi there. I've got AC and would like to clarify some thing. You say: >Don't be lost in this hint: >If 1000 days since the funeral passed and the tomb is not >dug over then the forgetful relatives wouldn't find the tomb >and wouldn't see its neighbors. I think this is incorrect. In fact (I got AC before looking at the webboard for the first time) I had the following code when checking whether the visit will succeed: if (time <= last_visit[visit_who] + 1000) //visit may happen, need to check other conditions else //visit impossible, they don't remember where the tomb is This must be what you mean, right? Well, I got WA on test 6 with this code, and got AC after removing this condition, so, the real condition to check if visit will succeed is whether anybody still affects - either the last visit of relatives, or the last visit of neighbours. Faint 1. During the funeral the friends don't notice anything around them... Faint 2. I got AC without maintaining heaps... const inp=''; out=''; daysize1=1001; daysize2=101; maxn=151; c:array[1..8,1..2] of longint=((-1,0),(1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)); type datatype=array[0..maxn*maxn] of longint; var client,size,ans,n,m:longint; treeperson,persontree,f,heavityperson,personheavity,h:datatype; procedure add(p,data:longint); begin while p<=size do begin inc(f[p],data); p:=p or (p-1)+1; end; end; function calc(p:longint):longint; var tmp:longint; begin tmp:=0; while p>0 do begin inc(tmp,f[p]); p:=p and (p-1); end; calc:=tmp; end; procedure heavity(p,nn:longint); var tmph,tmpp,j:longint; begin tmph:=h[p];tmpp:=heavityperson[p]; j:=p shl 1; while j<=nn do begin if (j<nn)and(h[j+1]<h[j]) then inc(j); if h[j]<tmph then begin h[p]:=h[j]; heavityperson[p]:=heavityperson[j]; personheavity[heavityperson[p]]:=p; p:=j;j:=p shl 1; end else j:=nn+1; end; h[p]:=tmph;heavityperson[p]:=tmpp; personheavity[heavityperson[p]]:=p; end; procedure updata(p:longint); var tmpp,tmph,j:longint; begin j:=p shr 1;tmph:=h[p];tmpp:=heavityperson[p]; while j>0 do if h[j]>tmph then begin h[p]:=h[j];heavityperson[p]:=heavityperson[j]; personheavity[heavityperson[p]]:=p; p:=j;j:=p shr 1; end else break; h[p]:=tmph;heavityperson[p]:=tmpp; personheavity[heavityperson[p]]:=p; end; procedure main; var nowx,z,nowy,xcurrent,ycurrent,now,w,current,l,r,day,d,i:longint; x:char; begin assign(input,inp);reset(input); readln(n,m);size:=n*m; w:=0; repeat read(day); while (w>0)and(h[1]<=day) do begin now:=heavityperson[1]; h[1]:=h[w]; heavityperson[1]:=heavityperson[w]; personheavity[heavityperson[1]]:=1; dec(w); if w>0 then heavity(1,w); add(persontree[now],-1); persontree[now]:=0; end; read(x); while (x<>'d')and(x<>'v') do read(x); if (x='d') then begin inc(client);l:=1;r:=size; if w<size then begin while l<r do begin d:=(l+r) shr 1; if calc(d)<d then r:=d else l:=d+1; end; add(r,1); treeperson[r]:=client; inc(w); heavityperson[w]:=client; h[w]:=day+daysize1; personheavity[client]:=w; persontree[client]:=r; updata(w); end else inc(ans); end else if x='v' then begin read(current); if persontree[current]>0 then begin h[personheavity[current]]:=day+daysize1; heavity(personheavity[current],w); xcurrent:=(persontree[current]-1) div m+1; ycurrent:=persontree[current]+m-xcurrent*m; for i:=1 to 8 do begin nowx:=xcurrent+c[i,1]; nowy:=ycurrent+c[i,2]; if (nowx>=1)and(nowx<=n)and(nowy>=1)and(nowy<=m) then z:=(nowx-1)*m+nowy else z:=0; if treeperson[z]>0 then if h[personheavity[treeperson[z]]]<day+daysize2 then begin h[personheavity[treeperson[z]]]:=day+daysize2; heavity(personheavity[treeperson[z]],w); end; end; end; end; until seekeof(input); assign(output,out);rewrite(output); writeln(ans); close(output); end; Begin Main; End. Const InFile = 'p1251.in'; OutFile = 'p1251.out'; Limit = 100; LimitNew = 10000; LimitQueue = 30000; Mask = 1 shl 9 - 1; dirx : array[1..8] of longint = (-1 , -1 , -1 , 0 , 0 , 1 , 1 , 1); diry : array[1..8] of longint = (-1 , 0 , 1 , -1 , 1 , -1 , 0 , 1); Type Tdata = array[1..Limit , 1..Limit] of record covered , lastvisit : longint; end; Tindex = array[1..LimitNew] of record x , y : longint; end; Tsum = array[1..Limit] of longint; Tkey = record time , x , y , sign , p : longint; end; Tqueue = array[1..LimitQueue] of Tkey; Var data : Tdata; sum : Tsum; index : Tindex; queue : Tqueue; N , M , total , ans , number : longint; procedure init; var i : longint; begin readln(N , M); fillchar(data , sizeof(data) , 0); fillchar(queue , sizeof(queue) , 0); fillchar(index , sizeof(index) , 0); for i := 1 to N do sum[i] := M; total := 0; end; procedure find_pos(var x , y : longint); begin x := 1; while (x <= N) and (sum[x] = 0) do inc(x); if x > N then x := 0 else begin y := 1; while data[x , y].covered <> 0 do inc(y); end; end; procedure process; var dir , nx , ny , p , newp : longint; key : Tkey; begin if queue[1].sign = 1 then if data[queue[1].x , queue[1].y].lastvisit < queue[1].time - 1000 then begin index[queue[1].p].x := 0; index[queue[1].p].y := 0; if odd(data[queue[1].x , queue[1].y].covered) then begin dec(data[queue[1].x , queue[1].y].covered); if data[queue[1].x , queue[1].y].covered = 0 then inc(sum[queue[1].x]); end; end; if queue[1].sign = 2 then if data[queue[1].x , queue[1].y].lastvisit < queue[1].time - 100 then begin for dir := 1 to 8 do begin nx := queue[1].x + dirx[dir]; ny := queue[1].y + diry[dir]; if (nx >= 1) and (ny >= 1) and (nx <= N) and (ny <= M) then begin p := data[nx , ny].covered; data[nx , ny].covered := data[nx , ny].covered and (Mask - 1 shl dir); if (p <> 0) and (data[nx , ny].covered = 0) then inc(sum[nx]); end; end; end; dec(total); if total <> 0 then begin key := queue[total + 1]; p := 1; while p * 2 <= total do begin newp := p; if queue[p * 2].time < key.time then newp := p * 2; if (p * 2 < total) and (queue[p * 2 + 1].time < key.time) and (queue[p * 2 + 1].time < queue[p * 2].time) then newp := p * 2 + 1; if newp = p then break; queue[p] := queue[newp]; p := newp; end; queue[p] := key; end; end; procedure shift(p : longint); var key : Tkey; begin p := total; key := queue[p]; while p <> 1 do if queue[p div 2].time > key.time then begin queue[p] := queue[p div 2]; p := p div 2; end else break; queue[p] := key; end; procedure add(time , x , y , num : longint); var dir , nx , ny : longint; begin data[x , y] I apologoze for wrong test and unclear text of "cemetry manager". Now some hints are added and set of tests is replaced. Thank Nikita Shamgunov for help. To the author: How come scanf("%d %d", &N, &M); while (N > 150 || M > 150) printf("muie\n"); gives TLE? The problem text is unclear, the example should have been explained. So please, keep your day job man!! Oh sorry, it gives Output Limit Exceeded (aah you get it) > To the author: > > How come > > scanf("%d %d", &N, &M); > while (N > 150 || M > 150) printf("muie\n"); > > gives TLE? > > The problem text is unclear, the example should have been explained. > So please, keep your day job man!! > > To the author: > > How come > > scanf("%d %d", &N, &M); > while (N > 150 || M > 150) printf("muie\n"); > > gives TLE? > > The problem text is unclear, the example should have been explained. > So please, keep your day job man!! > I agree, the text not complete why there is no information about the maximum number of event time? > #include <stdio.h> #include <stdlib.h> #define T1 1000 #define T2 100 #define NVEC 8 #define INF 66666 int Lasttime[10010]; int Clients; int Empty[10010], Canmove[10010]; #define time(i, j) (Time - Lasttime[Cl[i][j]]) int vi[8] = {0, 0, -1, 1, 1, -1, 1, -1}; int vj[8] = {1, -1, 0 ,0, -1, 1, 1, -1}; #define ni (i + vi[v]) #define nj (j + vj[v]) int Cl[210][210], N, M; int Time; void read_and_solve() { int i, j, x, v, fnd, Res = 0; char a; scanf("%d %d", &N, &M); Lasttime[0] = -INF; while (scanf("%d %c", &Time, &a) == 2) { if (a == 'v') { scanf("%d", &x); if (!Empty[x]) Lasttime[x] = Time; continue; } for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) if (Cl[i][j] && (!Empty[Cl[i][j]] || !Canmove[Cl[i][j]])) { if (time(i, j) > T1) Empty[Cl[i][j]] = 1; for (v = 0; v < NVEC; v++) if (ni > 0 && nj > 0 && ni <= N && nj <= M && Cl[ni][nj] && time(ni, nj) <= T2) break; if (v == NVEC) Canmove[Cl[i][j]] = 1; } Lasttime[++Clients] = Time; for (fnd = 0, i = 1; !fnd && i <= N; i++) for (j = 1; !fnd && j <= M; j++) if (Cl[i][j] == 0 || (Empty[Cl[i][j]] && Canmove[Cl[i] [j]])) Cl[i][j] = Clients, fnd = 1; if (!fnd) Res++; } printf("%d\n", Res); } int main() { read_and_solve(); return 0; } > I think that the maximal N and M in the tests are 200 > > I think that the maximal N and M in the tests are 200 > I think that the maximal N and M in the tests are 200 but not 100 The tests must be wrong - it's often f.e. : in acm.uva.es I think that the tests on Problem 1251 are wrong because N and M are greater than 100 What clients have been sent to a crematorium ??? 2 2 1: 1 d 2: 1 d 3: 1 d 4: 1 d 5: 300 d 500 v 2 6: 1001 d 7: 1002 d 8: 1002 d 9: 1003 v 3 10:1003 d 11:1003 d 1236 v 2 2032 v 2 12:2033 d I think 5,6,11,12 (4 clients) As far as I can judge, there is a misprint in the sample output. You are right, the correct answer should be four. Thus, let us wait a couple of days, until the consultation with the task author will be possible, and he will answer for sure. 2 2 1: 1 d 2: 1 d 3: 1 d 4: 1 d 5: 300 d 500 v 2 6: 1001 d 7: 1002 d 8: 1002 d 1003 v 3 9: 1003 d 10:1003 d 1236 v 2 2032 v 2 11:2033 d I think: First 2 clients in crematorium are 5 and 6. Next 3 clients are 8,9,10 because client-neighbour 7 is added recently. Last client is 11 because client-neighbour 2 is visited recently. Totally 6 clients are in the crematorium.‰ => 4 clear 1 d => 3 clear 1 d => 2 clear 1 d => 1 clear 1 d => 0 clear 300 d ->to the crematory 500 v 2 1001 d ->to the crematory => 3 clear 1002 d => 2 clear 1002 d => 1 clear 1003 v 3 1003 d => 0 clear 1003 d ->to the crematory 1236 v 2 => 3 clear 2032 v 2 2033 d => 2 clear 3 to clematory It is said "the manager puts a new client on a used place only if all the neighboring graves have not been visited for the last 100 days". So for 2x2 "2032 v 2" means all graves can't be used for clients until 2133. So last client must be in crematorium. I tried your interpretation but got WA 0.01 sec‰ > It is said "the manager puts a new client on a used place only if all the neighboring graves have not been visited for the last 100 days". > So for 2x2 "2032 v 2" means all graves can't be used for clients until 2133. > So last client must be in crematorium. > I tried your interpretation but got WA 0.01 sec‰ 2004 day manager clear all places except 2 (1236 v 2). 1. how many neighbours does a grave have(4 or 8)?(my answer:8) 2. if a coffin arives at time x what is the time when his grave will be emptied?(ex comes at day 1 leaves at time 1001 or 1002)(my answer 1001) 3. when a coffin arives is it considered visited?(does it affect his neighbours) (my answer : yes) 4. how do we number the coffins ?(my answer: after the number of their grave). If someone has different answers from those that I have please reply to this message.(I've tried also other combinations bot I still got WA) Please explain your answers. Thanks! 2. I think it is 1002 4. Clients are numbered by the order in which they come (i.e die) 5. What happens if someone comes to visit a client and his grave has already been emptied (like in the example i suppose, since clients 2 and 3 must have already been 'evacuated' if the correct output is really 3) ? > > > 1. how many neighbours does a grave have(4 or 8)?(my answer:8) > 2. if a coffin arives at time x what is the time when his grave will > be emptied?(ex comes at day 1 leaves at time 1001 or 1002)(my answer > 1001) > 3. when a coffin arives is it considered visited?(does it affect his > neighbours) (my answer : yes) > 4. how do we number the coffins ?(my answer: after the number of > their grave). > > If someone has different answers from those that I have please reply > to this message.(I've tried also other combinations bot I still got > WA) > Please explain your answers. > > Thanks! I think that when it sais 500 v 2 1003 v 3 1236 v 2 2032 v 2 in example it refers to the grave number 2 , respectively 3. Otherwise it doesn't make sense.In the problem is said that after 1000 days the friends and relatifs forget where the grave is(so why would they come to visit again).In this case the answer is realy 3. 1 d 1 d 1 d 1 d 300 d->to the crematory 500 v 2 1001 d 1002 d 1002 d 1003 v 3 1003 d->to the crematory 1003 d->to the crematory 1236 v 2 2032 v 2 2033 d In the text it clearly states that the number is the number of the client (not the grave or whatever) So it's weird Anyway in the example 2032 v 2 makes 2033 d go to the crematory (unless 2 is really client 2 and his grave was emptied and they don't visit anyone, just walk around the cemetery and can't remember where their departed friend is buried and they go home like morons). > I think that when it sais > 500 v 2 > 1003 v 3 > 1236 v 2 > 2032 v 2 > in example it refers to the grave number 2 , respectively 3. > Otherwise it doesn't make sense.In the problem is said that after > 1000 days the friends and relatifs forget where the grave is(so why > would they come to visit again).In this case the answer is realy 3. > 1 d > 1 d > 1 d > 1 d > 300 d->to the crematory > 500 v 2 > 1001 d > 1002 d > 1002 d > 1003 v 3 > 1003 d->to the crematory > 1003 d->to the crematory > 1236 v 2 > 2032 v 2 > 2033 d => 4 clear 1 d => 3 clear 1 d => 2 clear 1 d => 1 clear 1 d => 0 clear 300 d ->to the crematory 500 v 2 1001 d ->to the crematory => 3 clear 1002 d => 2 clear 1002 d => 1 clear 1003 v 3 1003 d => 0 clear 1003 d ->to the crematory 1236 v 2 => 3 clear 2032 v 2 2033 d => 2 clear 3 to clematory |
|