【题目链接】:http://codeforces.com/contest/765/problem/D

【题意】



给你一个函数f(x);

要让你求2个函数g[x]和h[x],使得g[h[x]] = x对1..m成立

h[g[x]] = f[x]对1..n成立;

这里

g[x]:[n]->[m];

h[x]:[m]->[n];

让你求h[x]的m的值,顺便输出两个函数的各个值

【题解】



这里要对f(x)做文章;

考虑f(x)==x的情况;

这时要想让

g[h[x]] = x对1..m成立

h[g[x]] = f[x]对1..n成立;

可以新加一个m;

h[++m] = x;

g[x] = m;

这样

g[h[m]] = m

h[g[x]] = x = f(x)

也成立了;

整个程序就以此为发生器;

求出了部分的g函数和全部的h函数(即只有f[x]==x的时候才能得出一个h函数);

之后对于那些还没有得到的g函数;

     rep1(i,1,n)

    {

        if (g[i]!=0) continue;

        if (h[g[f[i]]] == f[i])

            g[i] = g[f[i]];

        else

            return puts("-1"),0;

    }

这里

因为

g[x]:[n]->[m];

h[x]:[m]->[n];

所以h[g[f[i]]]返回的也是一个1..n的值,f[i]也是在1..n;

如果

h[g[f[i]]] == f[i]成立的话;

显然可以让g[i]=g[f[i]];

因为这样

h[g[i]] = f[i]就成立了；

(上面的过程就相当于在构造一个g[i]出来让h[g[i]]=f[i]成立);

而对于g[h[i]]=i (i∈[1..m])这个条件则不用管它了;

因为所有的h数组已经全部知道了,在上面f[i]==i那个判定的时候就已经保证了

g[h[i]]=i是恒成立的了;

脑洞比较大。。想不出来

当时做的时候就想着那么多人AC了;

肯定挺简单的吧;

就随便让g[1]=1,然后以这个为发生器搞整个g和h;

还是太年轻了。



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%I64d",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e6+100;

int n,m;

int f[N],g[N],h[N];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);

    rep1(i,1,n)

    {

        rei(f[i]);

        if (f[i]==i)

        {

            //g[h[i]] = i

            //h[g[i]] = f[i]

            h[++m] = i;

            g[i] = m;

        }

    }

    rep1(i,1,n)

    {

        if (g[i]!=0) continue;

        if (h[g[f[i]]] == f[i])

            g[i] = g[f[i]];

        else

            return puts("-1"),0;

    }

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

    rep1(i,1,n)

    {

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

        if (i==n)

            puts("");

        else

            putchar(' ');

    }

    rep1(i,1,m)

    {

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

        if (i==m)

            puts("");

        else

            putchar(' ');

    }

    return 0;

}