Codeforces #397 D. Artsem and Saunders

この回は出てたらレートを結構落としていたな…。
http://codeforces.com/contest/765/problem/D

問題

関数f:[1,n]→[1,n]が与えられる。
2つの関数g:[1,n]→[1,m]およびh:[1,m]→[1,n]のうち、g(h(x))=xかつh(g(x))=f(x)となるものが存在するなら、一例を答えよ。

解法

あるyに対し、f(x)=yとなるxの集合をS(y)とする。
条件を満たすには、各yに対しy∈S(y)であることが必要である。

yに対して1から順番に連番ID(y)を振る。
g(y)=ID(y)、h(ID(y))=yとすると、h(g(y))=yであり、かつg(h(y))=f(y)となる。

int N;
int F[101010];
vector<int> from[101010];
int rev[101010],to[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>F[i+1];
		from[F[i+1]].push_back(i+1);
	}
	int num=0;
	FOR(i,N) if(from[i+1].size()) {
		if(count(ALL(from[i+1]),i+1)==0) return _P("-1\n");
		to[i+1]=num+1;
		rev[num++]=i+1;
	}
	_P("%d\n",num);
	FOR(i,N) _P("%d ",to[F[i+1]]);
	_P("\n");
	FOR(i,num) _P("%d ",rev[i]);
	_P("\n");
	
	
}

まとめ

結構混乱した。