ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1156. Two Rounds

Why WA??
Posted by zhou MX 25 Mar 2002 16:49
program Ural_1156;
const
  maxn=100;
var
  map:array[1..maxn,1..maxn] of boolean;
  use:array[1..maxn] of integer;
  mem:array[1..maxn,0..maxn] of integer;
  n,l:integer;

procedure init;
var
  i,a,b,m:integer;
begin
  readln(n,m);
  n:=n+n;
  for i:=1 to m do
  begin
    readln(a,b);
    map[a,b]:=true; map[b,a]:=true;
  end;
end;

procedure search(x,g:integer);
var
  i:integer;
begin
  use[x]:=g;
  if g=1 then
  begin
    inc(mem[l,0]);
    mem[l,mem[l,0]]:=x;
  end;
  for i:=1 to n do
    if map[x,i] then
      if use[i]=0 then
        search(i,-g)
      else
      if use[i]=use[x] then
      begin
        writeln('IMPOSSIBLE');
        halt;
      end;
end;

procedure work;
var
  can:array[0..maxn] of boolean;
  way:array[1..maxn] of integer;
  i,j:integer;
begin
  for i:=1 to n do
    if use[i]=0 then
    begin
      l:=l+1;
      search(i,1);
    end;
  fillchar(can,sizeof(can),0);
  can[0]:=true;
  for i:=1 to l do
    for j:=n downto 0 do
      if can[j] and not can[j+mem[i,0]] then
      begin
        can[j+mem[i,0]]:=true;
        way[j+mem[i,0]]:=i;
      end;
  j:=n div 2;
  if not can[j] then
    writeln('IMPOSSIBLE')
  else begin
    fillchar(use,sizeof(use),0);
    while j<>0 do
    begin
      for i:=1 to mem[way[j],0] do
        use[mem[way[j],i]]:=1;
      j:=j-mem[way[j],0];
    end;
    j:=1;
    while use[j]=0 do
      j:=j+1;
    write(j);
    for i:=j+1 to n do
      if use[i]=1 then
        write(' ',i);
    writeln;
    j:=1;
    while use[j]=1 do
      j:=j+1;
    write(j);
    for i:=j+1 to n do
      if use[i]=0 then
        write(' ',i);
    writeln;
  end;
end;

begin
  init;
  work;
end.