AcWing 1579. 插入还是归并
原题链接
中等
作者:
RainSure
,
2022-02-25 19:01:47
,
所有人可见
,
阅读 136
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 110;
int a[maxn], b[maxn];
int n;
bool check()
{
for(int i = 1; i <= n; i ++){
if(a[i] != b[i]){
return false;
}
}
return true;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) cin >> b[i];
int p = 2;
while(p <= n && b[p] >= b[p - 1]) p ++;
int k = p;
while(p <= n && a[p] == b[p]) p ++;
if(p == n + 1){
cout << "Insertion Sort" << endl;
sort(b + 1, b + k + 1);
for(int i = 1; i <= n; i ++){
if(i != 1) cout << " ";
cout << b[i];
}
}else{
cout << "Merge Sort" << endl;
k = 1;
while(true)
{
bool flag = check();
int len = 1 << k;
for(int i = 1; i <= n; i += len){
sort(a + i, a + min(n + 1, i + len));
}
if(flag) break;
k ++;
}
for(int i = 1; i <= n; i ++) {
if(i != 1) cout << " ";
cout << a[i];
}
}
return 0;
}