牛客周赛 Round 40(补题）C题

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

小红拿到了一个长度为nnn的数组aaa，她希望你构造两个排列ppp和qqq，满足对于i∈[1,n],aii∈[1,n],a_ii∈[1,n],ai​为pip_ipi​或qiq_iqi​二选一。你能帮帮她吗？

定义排列是一个长度为nnn的数组，其中1到nnn每个元素恰好出现1次。

输入描述:

第一行输入一个正整数nnn，代表两个数组的长度。
第二行输入nnn个正整数aia_iai​。
1≤n≤1051\leq n \leq 10^51≤n≤105
1≤ai≤n1\leq a_i \leq n1≤ai​≤n

输出描述:

如果无解，请输出-1。
否则第一行输出nnn个正整数pip_ipi​，第二行输出nnn个正整数qiq_iqi​，代表小红构造的两个排列。有多解时输出任意即可。

示例1

输入

复制3 2 3 2

3
2 3 2

输出

复制2 3 1 1 3 2

2 3 1
1 3 2

示例2

输入

复制4 1 1 1 1

4
1 1 1 1

输出

复制-1

-1

解析：

对set不太熟悉。

只需要开启连个set 对其进行查询：

最后 ，只用set *begin()添加进容器中。

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define N 100000
void solve_case() {
	int i,j,k,n,m,t,f1[N+50],f2[N+50],a[N+50];
	set<int> s1,s2;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >>a[i];
		s1.insert(i);
		s2.insert(i);
	}
	for(int i = 1;i <= n;i++)
	{
		if(s1.count(a[i]))
		{
			f1[i] = a[i];
			s1.erase(a[i]);
		}else if(s2.count(a[i]))
		{
			f2[i] = a[i];
			s2.erase(a[i]);	
		}		
		else{
			cout <<"-1";
			return;
		}
	}
	for(i = 1;i <= n;i++)
	{
		if(!f1[i])
		{
			f1[i] = *s1.begin();
			s1.erase(f1[i]);
		}
		if(!f2[i]){
			f2[i] = *s2.begin();
			s2.erase(f2[i]);
		}
	}
	for(i = 1;i <= n;i++)
	{
		cout << f1[i]<<" ";
	}
	cout<<endl;
	for(i = 1;i <= n;i++)
	{
		cout << f2[i]<<" ";
	}
	cout<<endl;
	
	
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve_case();
    }
}