Codeforces Round #397 (Div. 1 + Div. 2 combined) D. Artsem and Saunders 构造

D. Artsem and Saunders

链接：

http://codeforces.com/contest/765/problem/D

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<map>
 5 using namespace std;
 6 
 7 const int maxn = 1e5 + 7;
 8 int f[maxn], h[maxn], g[maxn];
 9 map<int, int>F;
10 
11 int main()
12 {
13     int n;
14     scanf("%d", &n);
15     for (int i = 1; i <= n; i++) scanf("%d", f + i);
16     int m = 0;
17     for (int i = 1; i <= n; i++) { 
18         if (F[f[i]] == 0){
19             m++;
20             h[m] = f[i]; 
21             F[f[i]] = m; 
22         }
23         g[i] = F[f[i]]; 
24     }
25     for (int i = 1; i <= m; i++){
26         if (g[h[i]] != i) {
27             printf("-1
");
28             return 0;
29         }
30     }
31     printf("%d
", m);
32     for (int i = 1; i <= n; i++) printf("%d ", g[i]);
33     printf("
");
34     for (int i = 1; i <= m; i++) printf("%d ", h[i]);
35     printf("
");
36     return 0;
37 }