AtCoders's practice task B. Interactive sort

help
1

Problem.

I first implemented merge sort for this, that didn’t stand any test cases.

then i used inbuilt sort with a comparator to do the interaction.

but this one also fails radomly on half of test cases.

My code :

#include <iostream>
#include <algorithm>
using namespace std;

bool known[27][27] ={0};
bool g__[27][27] = {0};
bool ismin(int a, int b){
  if (known[a][b]) return g__[a][b];
  cout << "? " << (char)(a + 65) << ' ' << (char)(b + 65) << '\n';
  char temp; cin >> temp;
  if (temp == '<') { g__[a][b] = true; g__[b][a] = false; }
  if (temp == '>') { g__[a][b] = false; g__[b][a] = true; }
  known[a][b] = known[b][a] = true;
  return (temp == '<');
}

int main() {
  int n, q; cin >> n >> q;
  int Arr[n];
  for (int i = 0 ; i < n ; i++) Arr[i] = i;
  sort(Arr,Arr+n,ismin);
	cout << "! ";
  for (int i:Arr)cout << (char)(i+65) ;
  return 0;
}

Edit Merge sort didn’t failed compleletly, i was submitting in the wrong problem. but still that didn’t passes all cases.

2

If you want to know why this is failing
the reason is tight cases, this will pass only bound of 1000.
and (5,7) is even tighter than (26,100).