NC53682. 「木」揠苗助长
描述
帕秋莉掌握了一种木属性魔法
这种魔法可以使植物迅速地长高
为了记录植物的生长情况，帕秋莉让小A和小B分别记录当日每株植物的高度
输入描述
第一行一个整数n，表示共有n棵植物
接下来两行各n个数，分别代表两人记录的序列
两人记录的高度与真正的高度都只有一个数有差异
输出描述
如果无法恢复原序列，输出“Impossible”（不含引号）
否则输出原序列，如果有多种可能，输出字典序最小的一种
示例1
输入:
6 1 2 3 6 5 6 1 2 2 6 5 4
输出:
1 2 3 6 5 4
C++(clang++11) 解法, 执行用时: 60ms, 内存消耗: 7192K, 提交时间: 2020-12-02 22:09:02
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
vector<int> vv[N];
int main()
{
int n,x=-1,y=-1;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
vv[a[i]].push_back(i);
}
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
{
if( vv[i].size() == 2 )
x = i;
if( vv[i].size() == 0 )
y = i;
}
if( x == -1 || y == -1 )
{
printf("Impossible\n");
return 0;
}
if( x < y )
{
a[vv[x][0]] = x;
a[vv[x][1]] = y;
}
else
{
a[vv[x][0]] = y;
a[vv[x][1]] = x;
}
int f=0;
for(int i=0;i<n;i++)
{
if( a[i] != b[i] )
{
f++;
}
}
if( f == 1 )
{
for(int i=0;i<n;i++)
printf("%d\n",a[i]);
return 0;
}
swap(a[vv[x][1]],a[vv[x][0]]);
f = 0;
for(int i=0;i<n;i++)
{
if( a[i] != b[i] )
{
f++;
}
}
if( f == 1 )
{
for(int i=0;i<n;i++)
printf("%d\n",a[i]);
return 0;
}
else
printf("Impossible\n");
return 0;
}
C++14(g++5.4) 解法, 执行用时: 71ms, 内存消耗: 7140K, 提交时间: 2019-11-23 19:26:56
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int>v[100010];
int a[100010],b[100010];
int x=-1,y=-1;
int main(){
int n;scanf("%d",&n);
for (int i=0;i<n;i++){
scanf("%d",a+i);
v[a[i]].push_back(i);
}
for (int i=0;i<n;i++)scanf("%d",b+i);
for (int i=1;i<=n;i++){
if (v[i].size()==2)x=i;
if (v[i].size()==0)y=i;
}
if (x==-1||y==-1){
puts("Impossible");
return 0;
}
if (x<y)a[v[x][0]]=x,a[v[x][1]]=y;
else a[v[x][0]]=y,a[v[x][1]]=x;
int flag=0;
for (int i=0;i<n;i++)if (a[i]!=b[i]){flag++;}
if (flag==1){
for (int i=0;i<n;i++)printf("%d\n",a[i]);
return 0;
}
swap(a[v[x][0]],a[v[x][1]]);
flag=0;
for (int i=0;i<n;i++)if (a[i]!=b[i]){flag++;}
if (flag==1){
for (int i=0;i<n;i++)printf("%d\n",a[i]);
return 0;
}
puts("Impossible");
}