PAT (Advanced Level) Practice - 1098 Insertion or Heap Sort（25 分）

1.#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
int a[110], b[110];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    int i;
    for(i=1;i<n;)
        if(b[i]>=b[i-1]) i++;
        else break;
    int p=i, isIns=1;
    for(;i<n;i++)
        if(a[i]!=b[i]){isIns=0; break;}
    if(isIns)
    {
        puts("Insertion Sort");
        sort(b,b+p+1);
    }
    else
    {
        for(i=n-1;i>0;)
            if(b[i]>=b[i-1]) i--;
            else break;
        puts("Heap Sort");
        pop_heap(b,b+i+1);
    }
    for(i=0;i<n;i++)
        printf("%d%c",b[i],i==n-1?'\n':' ');
    return 0;
}