Description

Input

Output

Sample Input

Sample Output

HINT

正解：匈牙利算法。

這題給他們考試。。沒(méi)人想到二分圖匹配。有兩人想到用網(wǎng)絡(luò)流做可行解，給了4分部分分，其他人都是爆搜。。實(shí)在覺(jué)得這題不是很難吧。。

看完題目以后就能發(fā)現(xiàn)這是一道裸的二分圖匹配。如果用網(wǎng)絡(luò)流做，dinic無(wú)法保證最優(yōu)解，EK會(huì)超時(shí)。那么可以考慮用匈牙利算法。只要保證遍歷與一個(gè)點(diǎn)相連的邊按照相連點(diǎn)從小到大的順序就行，因?yàn)閷?duì)于單一的一個(gè)點(diǎn)來(lái)說(shuō)，如果增廣了一條路徑就不會(huì)再增廣了。而對(duì)于全局則從最后一個(gè)點(diǎn)開(kāi)始增廣，因?yàn)楹笤鰪V的路徑會(huì)覆蓋掉先增廣的路徑。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;int g[30010][5],match[30010],vis[30010],n;il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il int dfs(RG int x,RG int cnt){    for (RG int i=1;i<=2;++i){	RG int v=g[x][i]; if (vis[v]==cnt) continue; vis[v]=cnt;	if (match[v]==-1 || dfs(match[v],cnt)){	    match[v]=x,match[x]=v; return 1;	}    }    return 0;}il void work(){    n=gi(); RG int x,flag=1,cnt=0;    for (RG int i=0;i<n;++i){	x=gi(); g[i][1]=i+x; if (g[i][1]>=n) g[i][1]-=n;	g[i][2]=i-x; if (g[i][2]<0) g[i][2]+=n;	if (g[i][1]>g[i][2]) swap(g[i][1],g[i][2]);	g[i][1]+=n,g[i][2]+=n;    }    memset(match,-1,sizeof(match));    for (RG int i=n-1;i>=0;--i) if (!dfs(i,++cnt)){ flag=0; break; }    if (!flag){ PRintf("No Answer"); return; } printf("%d",match[0]-n);    for (RG int i=1;i<n;++i) printf(" %d",match[i]-n); return;}int main(){    File("transform");    work();    return 0;}