Bzoj1562

,

Solution

先建出二分图。

考虑字典序最小。从后向前跑匈牙利即可。因为 $i$ 小的会覆盖到 $i$ 大的。

然后就好了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long 
#define maxn 20005
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
int n,cnt,ans,vis[maxn],match[maxn];
vector<int>to[maxn];
inline bool dfs(int x) {
	int i;
	for (auto y:to[x])
	    if (vis[y]!=cnt) {
	    	vis[y]=cnt;
	    	if (!match[y]||dfs(match[y])) {
	    		return match[y]=x,match[x]=y,1;
			}
		}
	return 0;
}
inline int id(int x) {
	if (x<0) return x+n;
	else if (x>=n) return x-n;
	else return x;
}
inline void ins(int x,int y,int z) {
	if (y>z) swap(y,z);
	to[x].push_back(y);
	to[x].push_back(z);
//	printf("%d %d %d\n",x,y-n,z-n);
}
signed main(void){
    int i,x,j;
    read(n);
    for (i=0;i<n;i++) read(x),ins(i,id(i-x)+n,id(i+x)+n);
    for (i=n-1;i>=0;i--) {
    	++cnt;ans+=dfs(i);
	}
	if (ans<n) return puts("No Answer"),0; 
	for (i=0;i<n;i++) printf("%d ",match[i]-n);
	return 0;
}