1562: [NOI2009]变换序列

Description

Input

Output

Sample Input

1 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的数据中N≤50；
60%的数据中N≤500；
100%的数据中N≤10000。

二分图匹配，倒着匹配，每次选小的增广（随便乱yy一下，应该就可以证明是字典序最小的吧）

 1 const
 2     maxn=10010;
 3 var
 4     first,link:array[0..maxn]of longint;
 5     a:array[0..maxn,0..1]of longint;
 6     next,last:array[0..maxn]of longint;
 7     n:longint;
 8 
 9 procedure swap(var x,y:longint);
10 var
11     t:longint;
12 begin
13     t:=x;x:=y;y:=t;
14 end;
15 
16 procedure init;
17 var
18     i,x:longint;
19 begin
20     read(n);
21     for i:=1 to n do
22       begin
23         read(x);
24         a[i,0]:=i+x;
25         a[i,1]:=i-x;
26         if a[i,0]>n then dec(a[i,0],n);
27         if a[i,1]<1 then inc(a[i,1],n);
28         if a[i,0]>a[i,1] then swap(a[i,0],a[i,1]);
29       end;
30 end;
31 
32 var
33     time:longint;
34     flag:array[0..maxn]of longint;
35 
36 function path(x:longint):boolean;
37 var
38     i:longint;
39 begin
40     for i:=0 to 1 do
41       if (i=0) or (a[x,i]<>a[x,i-1]) then
42         if flag[a[x,i]]<>time then
43         begin
44           flag[a[x,i]]:=time;
45           if (link[a[x,i]]=0) or (path(link[a[x,i]])) then
46           begin
47             link[a[x,i]]:=x;
48             exit(true);
49           end;
50         end;
51     exit(false);
52 end;
53 
54 procedure work;
55 var
56     i:longint;
57 begin
58     for i:=n downto 1 do
59       begin
60         inc(time);
61         if path(i)=false then
62         begin
63           writeln('No Answer');
64           exit;
65         end;
66       end;
67     for i:=1 to n do
68       if link[a[i,0]]=i then write(a[i,0]-1,' ')
69       else write(a[i,1]-1,' ');
70 end;
71 
72 begin
73     init;
74     work;
75 end.

View Code