ARMY.cpp

#include <iostream>
using namespace std;
 
int NG, NM;
 
void Merge(int *a, int left, int m, int right)
{
    int l = left, r = m + 1, k = 0;
    int *temp = new int[right - left + 1];
 
    while(l <= m && r <= right)
    {
        if(a[l] < a[r]) temp[k++] = a[l++];
        else temp[k++] = a[r++];
    }
 
    while(l <= m) temp[k++] = a[l++];
    
    while(r <= right) temp[k++] = a[r++];
 
    for(int i = 0; i < k; i++)
        a[left + i] = temp[i];
 
    delete[] temp;
}
 
void MergeSort(int *a, int left, int right)
{
    int m;
    if(left < right)
    {
        m = (left + right)/2;
        MergeSort(a, left, m);
        MergeSort(a, m + 1, right);
        Merge(a, left, m, right);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
 
    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);
 
    int Testcase = 0;
    cin >> Testcase;
 
    for(int tc = 0; tc < Testcase; tc++)
    {
        cin >> NG >> NM;
 
        int *ng_army = new int[NG];
        for(int i = 0; i < NG; i++)
            cin >> ng_army[i];
 
        int *nm_army = new int[NM];
        for(int i = 0; i < NM; i++)
            cin >> nm_army[i];
 
        // Sắp xếp sức mạnh của quái vật theo chiều độ mạnh tăng dần
        MergeSort(ng_army, 0, NG-1);
        MergeSort(nm_army, 0, NM-1);
 
        // 2 con trỏ vào 2 mảng, để duyệt lần lượt các phần tử
        int ig = 0, im = 0;
        while(ig < NG && im < NM)
        {
            // nếu độ mạnh quái vật ở đội MechaGodzilla <= độ mạnh 
            // quái vật ở đội Godzilla thì quái vật đội MechaGodzilla sẽ chết
            // ngược lại thì quái vật đội Godzilla sẽ chết.
            // thực tế, sẽ luôn tồn tại 1 đội thắng
            if(nm_army[im] <= ng_army[ig]) im++;
            else if(nm_army[im] > ng_army[ig]) ig++;
        }
 
        // Đội nào vẫn còn quái vật thì sẽ thắng
        if(ig < NG) cout << "Godzilla" << endl;
        else cout << "MechaGodzilla" << endl;
 
        delete[] ng_army;
        delete[] nm_army;
    }
 
    return 0;
}