记录编号	60221	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]变换序列	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2013-05-19 18:37:54	内存使用	0.66 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int SIZEN=10001;
int N;
//我们把T序列用T标识(左边),原序列用R标识(右边)
int d[SIZEN]={0};
vector<int> ct[SIZEN];//每一半的邻接表
int matcht[SIZEN]={0};
vector<int> cr[SIZEN];
int matchr[SIZEN]={0};
//两边都是0~n-1这样的
void swap(int &a,int &b);//谭浩强(Cat Mario)的代码风格
void addedge(int a,int b);
bool init(void);
bool exc(int x,int k);
bool expand(int x);
bool work(void);
void write(void);
int main(){
	freopen("transform.in","r",stdin);
	freopen("transform.out","w",stdout);
	bool flag;
	flag=init();
	if(!flag) goto END;
	flag=work();
	if(!flag) goto END;
	write();
	return 0;
	END:;
	printf("No Answer\n");
}
void write(void){
	int i;
	for(i=0;i<N;i++) cout<<matcht[i]<<" ";
	cout<<endl;
}
bool work(void){
	int i;
	for(i=0;i<N;i++){
		if(matcht[i]==-1){//未配
			if(!exc(i,-1)) return false;//让这个值卖个萌,以达到尝试两次的效果
		}
	}
	return true;
}
bool exc(int x,int k){//左边的x,排除k
	int i;
	bool flag=false;
	for(i=0;i<ct[x].size();i++){
		if(ct[x][i]==k) continue;
		if(matchr[ct[x][i]]!=-1){//失败
			matcht[x]=-1;
			return false;
		}
		matcht[x]=ct[x][i];
		matchr[ct[x][i]]=x;
		if(expand(ct[x][i])) return true;
	}
	if(!flag) matcht[x]=-1;
	return flag;
}
bool expand(int x){//右边的x
	int i;
	for(i=0;i<cr[x].size();i++){
		if(matcht[cr[x][i]]!=-1) continue;
		if(!exc(cr[x][i],x)){
			matchr[x]=-1;
			return false;
		}
	}
	return true;
}
void addedge(int a,int b){//T的a到R的b
	ct[a].push_back(b);
	cr[b].push_back(a);
}
void swap(int &a,int &b){
	int temp=a;a=b;b=temp;
}
bool init(void){
	scanf("%d",&N);
	int i;
	for(i=0;i<N;i++){
		scanf("%d",&d[i]);
		if(d[i]*2>N) return false;
	}
	int n1,n2;
	for(i=0;i<N;i++){
		n1=(i+d[i])%N;
		n2=(i-d[i]+N)%N;
		if(n1>n2) swap(n1,n2);
		addedge(i,n1);
		if(n2!=n1) addedge(i,n2);
	}
	for(i=0;i<N;i++) matcht[i]=matchr[i]=-1;
	return true;
}