OJ Board

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.