I get WA over and over...
My program gives correct output for all tests from the original olimpiad's site! I'am confused and frustrated...
I used disjoint sets (which is natural for this problem).
Code: Select all
program kp10960;
// The Party, Part II
const
UNDEFINED = 255;
label finish;
var
t, n, c: integer;
p: array [0..100,0..25] of byte;
rank: array [0..100,0..25] of byte;
notc: array [0..25,0..100,0..100] of byte;
col: array [0..25,0..100] of byte;
procedure init;
begin
readln(t);
end;
function parent(man, item: integer): integer;
begin
if p[item,man]<>man then
p[item,man]:= parent(p[item,man],item);
result:= p[item,man];
end;
function color(man, item: integer): integer;
begin
result:= col[parent(man,item),item];
end;
procedure union(item, man1, man2: integer);
var
i: integer;
begin
man1:= parent(man1,item);
man2:= parent(man2,item);
if man1=man2 then exit;
if rank[item,man1]>rank[item,man2] then begin
p[item,man2]:= man1;
for i:=0 to c-1 do notc[man1,item,i]:= notc[man1,item,i] or notc[man2,item,i];
end else begin
p[item,man1]:= man2;
for i:=0 to c-1 do notc[man2,item,i]:= notc[man1,item,i] or notc[man2,item,i];
if rank[item,man2]=rank[item,man1] then
inc(rank[item,man2]);
end;
end;
procedure trim(var s: string);
var
i: integer;
begin
while (length(s)>1) and (not (s[1] in ['A'..'Z','a'..'z','0'..'9'])) do delete(s,1,1);
while (length(s)>1) and (not (s[length(s)] in ['A'..'Z','a'..'z','0'..'9'])) do delete(s,length(s),1);
i:= 2;
while i<=length(s) do begin
if (s[i]=' ') and (s[i-1]=' ') then
delete(s,i,1)
else inc(i);
end;
end;
procedure solve;
var
i, j, ii, u, ps, item, l, k, clr, vars: integer;
s, s1: string;
v: array [0..25] of byte;
found: boolean;
f: integer;
begin
for i:= 1 to t do begin
readln;
readln(n, ii, c, u);
fillchar(notc,sizeof(notc),0);
fillchar(col,sizeof(col),UNDEFINED);
for j:=0 to n-1 do begin
for k:=0 to ii-1 do begin
rank[k,j]:= 0;
p[k,j]:= j;
end;
end;
found:= true;
for j:=1 to u do begin
readln(s);
trim(s);
ps:= pos('item',s);
s1:= copy(s,1,ps-1);
fillchar(v,sizeof(v),0);
item:= ord(s[ps+5])-ord('0');
if s[ps+6] in ['0'..'9'] then item:= item*10+(ord(s[ps+6])-ord('0'));
l:= length(s);
for k:=ps+4 to l do
if s[k] in ['A'..'Z'] then v[ord(s[k])-ord('A')]:= 1;
if pos('Same',s1) <> 0 then begin
k:=0;
while (k<n) and (v[k]=0) do inc(k);
if k=n then begin
found:= false;
break;
end;
f:= k; inc(k);
while k<n do begin
if v[k]=1 then begin
if color(f,item)=UNDEFINED then
if color(k,item)=UNDEFINED then
union(item,f,k)
else begin
clr:= color(k,item);
union(item,f,k);
if notc[parent(k,item),item,clr]=1 then begin
found:= false;
break;
end else col[parent(k,item),item]:= clr;
end
else
if color(k,item)=UNDEFINED then begin
clr:= color(f,item);
union(item,f,k);
if notc[parent(k,item),item,clr]=1 then begin
found:= false;
break;
end else col[parent(k,item),item]:= clr;
end else if color(k,item)<>color(f,item) then begin
found:= false;
break;
end;
end;
inc(k);
end;
end else if pos('Not',s1)<>0 then begin
clr:= ord(s[ps-6])-ord('0');
if s[ps-7] in ['0'..'9'] then inc(clr,10*(ord(s[ps-7])-ord('0')));
for k:=0 to n-1 do
if (v[k]=1) and (color(k,item)=clr) then begin
found:= false;
break;
end else if (v[k]=1) then begin
notc[parent(k,item),item,clr]:= 1;
end;
end else begin
clr:= ord(s[ps-6])-ord('0');
if s[ps-7] in ['0'..'9'] then inc(clr,10*(ord(s[ps-7])-ord('0')));
for k:=0 to n-1 do
if v[k]=1 then
if (color(k,item) = UNDEFINED) then
if notc[parent(k,item),item,clr]=1 then begin
found:= false;
break;
end else col[parent(k,item),item]:= clr
else if color(k,item) <> clr then begin
found:= false;
break;
end;
end;
if not found then break;
end;
if not found then writeln('Contradiction')
else begin
for j:=0 to n-1 do begin
for k:=0 to ii-1 do
if color(j,k) = UNDEFINED then begin
u:= parent(j,k);
vars:= 0; clr:= 0;
for f:=0 to c-1 do
if notc[u,k,f]=0 then begin
inc(vars);
clr:= f;
end;
if vars=0 then begin
found:= false;
break;
end;
if vars=1 then col[u,k]:= clr;
end;
if not found then break;
end;
if not found then writeln('Contradiction')
else begin
for j:=0 to n-1 do begin
write(chr(ord('A')+j),' ');
for k:=0 to ii-1 do
if color(j,k)=UNDEFINED then begin
write('?');
if k<>ii-1 then write(' ');
end else begin
write(color(j,k));
if k<>ii-1 then write(' ');
end;
writeln;
end;
end;
end;
if i<>t then writeln;
end;
end;
procedure print;
begin
end;
begin
{$IFNDEF ONLINE_JUDGE}
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
{$ENDIF}
init;
solve;
print;
finish:
{$IFNDEF ONLINE_JUDGE}
close(input); close(output);
{$ENDIF}
end.
).
