C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 580K, 提交时间: 2020-08-02 11:06:14

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=4e4+5;
int Next[N][2];
int n;
bool v[N];int match[N];
int ans[N];
bool dfs(int x){
    for(int i=0;i<=1;i++){
        int y=Next[x][i];
        if(v[y]) continue;
        v[y]=1;
        if(match[y]==-1||dfs(match[y])){
            match[y]=x;
            ans[x]=y;
            return 1;
        }
    }return 0;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        Next[i][0]=(i+x)%n;
        Next[i][1]=(i-x+n)%n;
        if(Next[i][0]>Next[i][1]) swap(Next[i][0],Next[i][1]);
        match[i]=-1;
    }
    
    for(int i=n-1;i>=0;i--){
        memset(v,0,sizeof(v));
        if(!dfs(i)){
            cout<<"No Answer";return 0;
        }
    }
    for(int i=0;i<n;i++){
        if(i!=n-1) cout<<ans[i]<<' ';
        else cout<<ans[i];
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 29ms, 内存消耗: 748K, 提交时间: 2019-04-02 17:28:04

#include<bits/stdc++.h>
using namespace std;
const int N = 110000;
int n,v;
int d[N],s[N][2],vis[N],to[N],lykkk[N];
bool hungry(int u){
	for(int i=0;i<=1;++i) 
		if(!vis[s[u][i]]){
			int v=s[u][i];
			vis[v]=1;
			if(lykkk[v]==-1 || hungry(lykkk[v])){
				lykkk[v]=u;
				to[u]=v;
				return 1;
			}
		}
	return 0;
}
int main(){
	cin>>n;
	for(int i=0;i<=n-1;++i) cin>>d[i];
	for(int i=0;i<=n-1;++i){
		s[i][0]=(i+d[i]+n)%n;
		s[i][1]=(i-d[i]+n)%n;
		if(s[i][0]>s[i][1]) swap(s[i][0],s[i][1]);
		lykkk[i]=to[i]=-1;
	}
	for(int i=n-1;i>=0;--i){
		for(int j=0;j<=n-1;++j) vis[j]=0;
		if(!hungry(i)){
			cout<<"No Answer";
			return 0;
		}
	}
	for(int i=0;i<=n-1;++i) cout<<to[i]<<" ";
	return 0;
}