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.