【构造】Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined) D. Artsem and Saunders

根据那两个式子

g(h(x))=x

h(g(x))=f(x)

可以推出来两个新的式子

g(f(x))=g(x)

h(x)=f(h(x))

于是，我们先找到f(x)的所有不动点，有几个不动点，m就是多少，将它们依次赋值给h(1),h(2),...,h(m)，对应的g(h(i))赋值成1,2,..,m

然后如果对于某个i，g(f(i))不存在的话，则无解，否则有解，将g和h依次输出即可。

#include<cstdio>

using namespace std;

int n,f[100010],g[100010],h[1000010],m;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	  scanf("%d",&f[i]);

	for(int i=1;i<=n;++i)

	  if(f[i]==i)

	    {

	      h[++m]=i;

	      g[i]=m;

	    }

	if(!m)

	  {

	  	puts("-1");

	  	return 0;

	  }

	for(int i=1;i<=n;++i)

	  if(!g[f[i]])

	    {

	      puts("-1");

	      return 0;

	    }

	printf("%d\n",m);

	for(int i=1;i<n;++i)

	  printf("%d ",g[f[i]]);

	printf("%d\n",g[f[n]]);

	for(int i=1;i<m;++i)

	  printf("%d ",h[i]);

	printf("%d\n",h[m]);

	return 0;

}

巴特西

【构造】Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined) D. Artsem and Saunders

最新文章

热门文章