Program p1019; Const MaxN = 6000; Var S : Array[1..MaxN, 1..2]of Longint; Del : Array[1..MaxN]of Byte; N, s0, ai, bi : Longint; ci : Char; Procedure Check; Var i, j, k : Longint; begin k := 0; for i := 1 to s0 do begin if i > s0 - k then break; if (Del[i] = 1) or (S[i, 1] = S[i, 2]) then begin k := k + 1; for j := i to s0 - 1 do S[j] := S[j + 1]; end; end; s0 := s0 - k; end; Procedure Black; Var i, ts0 : Longint; begin FillChar(Del, SizeOf(Del), 0); ts0 := s0; for i := 1 to s0 do if (ai <= S[i, 1]) and (bi >= S[i, 1]) and (bi <= S[i, 2]) then S[i, 1] := bi else if (ai >= S[i, 1]) and (ai <= S[i, 2]) and (bi >= S[i, 2]) then S[i, 2] := ai else if (ai <= S[i, 1]) and (bi >= S[i, 2]) then Del[i] := 1 else if (ai >= S[i, 1]) and (bi <= S[i, 2]) then begin ts0 := ts0 + 1; S[ts0, 1] := bi; S[ts0, 2] := S[i, 2]; S[i, 2] := ai; end; s0 := ts0; Check; end; Procedure Merge; Var i, j : Longint; ex : Boolean; begin FillChar(Del, SizeOf(Del), 0); While True do begin ex := true; for i := 1 to s0 - 1 do if Del[i] = 0 then for j := i + 1 to s0 do if Del[j] = 0 then if (S[i, 1] <= S[j, 1]) and (S[i, 2] >= S[j, 1]) then begin if S[j, 2] > S[i, 2] then S[i, 2] := S[j, 2]; Del[j] := 1; ex := false; end else if (S[i, 1] <= S[j, 2]) and (S[i, 2] >= S[j, 2]) then begin if S[j, 1] <= S[i, 1] then S[i, 1] := S[j, 1]; Del[j] := 1; ex := false; end else if (S[i, 1] >= S[j, 1]) and (S[i, 2] <= S[j, 2]) then begin Del[i] := 1; ex := false; end else if (S[j, 1] >= S[i, 1]) and (S[j, 2] <= S[i, 2]) then begin Del[j] := 1; ex := false; end; if ex then break; end; end; Procedure WriteIt; Var L, R, i : Longint; begin L := 0; R := 0; for i := 1 to s0 do if (S[i, 2] - S[i, 1] > R - L) or ((S[i, 2] - S[i, 1] = R - L) and (S[i, 1] < L)) then begin L := S[i, 1]; R := S[i, 2]; end; Writeln(L, ' ', R); end; begin S[1, 1] := 0; S[1, 2] := 1000000000; s0 := 1; Readln(N); While N > 0 do begin N := N - 1; Readln(ai, bi, ci, ci); if ai >= bi then Continue; if ci = 'b' then Black else begin s0 := s0 + 1; S[s0, 1] := ai; S[s0, 2] := bi; end; end; Merge; WriteIt; end. INPUT: 14 1 999999999 b 1 300 b 20 120 w 1 50 b 220 300 w 250 270 b 40 70 w 50 160 b 30 90 w 120 140 w 40 50 b 180 200 w 1 40 w 70 80 w OUTPUT: 0 40 Hope it can help.If still not,I can give you more test data. my program made the correct answer for the test case above, but WA at #2 on the judge, could you give me some more tests? Thank you very much! input 9 2 34 w 1 95 b 33 875 b 34 543 w 33 762 b 98754 999999843 b 87 221 w 76 432 w 325 764 b output 76 325 if you want more test mail me Hanieh_Mirzaei@yahoo.com I thought your test is incorrect. I solve it by hand and I found the answer should be 875 98754,isn't it? I have the same problem (WA on #2). I checked this test and it sould be 875 98754. why is it 76 325 ?? ...well i also wa on test 2 but the 1st test my answer is 60 140 the 2nd the same as upstairs i'm wa on test 8 now ... Edited by author 27.11.2005 20:47 Edited by author 27.11.2005 20:48 Edited by author 27.11.2005 20:49 thanks very much for your test date,because of then test date,i found what is wrong with my program 14 1 999999999 b 1 300 b 20 120 w 1 50 b 220 300 w 250 270 b 40 70 w 50 160 b 30 90 w 120 140 w 40 50 b 180 200 w 1 40 w 70 80 w The answer isn't 50 90? Where did it say that 0 is white? Edward, I think in this test 1 40 Edited by author 19.05.2012 22:24 Hi, I have tried out many tests and they are all passing. However, I get "Wrong answer" in test #1 and stuck up there. Can u give me test cases for test #1 ? |