In this HackerEarth Mind Palaces problem solution, Sherlock Holmes loves mind palaces! We all know that.

A mind palace, according to Mr. Holmes is something that lets him retrieve a given memory in the least time possible. For this, he structures his mind palace in a very special way. Let an NxM Matrix denote the mind palace of Mr. Holmes. For fast retrieval, he keeps each row and each column sorted. Now given a memory X, you have to tell the position of the memory in Sherlock's mind palace.


HackerEarth Mind Palaces problem solution


HackerEarth Mind Palaces problem solution.

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<map>
#define rep(i,N) for(int (i)=0;(i)<(N);(i)++)
#define repi(i,j,N) for(int (i)=(j);(i)<(N);(i)++)
#define repg(i,j,N) for((i)=(j);(i)<(N);(i)++)
#define si(i) scanf("%d",&(i))
#define sl(i) scanf("%lld",&(i))
#define pi(i) printf("%d",(i))
#define pl(i) printf("%lld",(i))
#define pin(i) printf("%d\n",(i))
#define pln(i) printf("%lld\n",(i))
#define pw    printf(" ");
#define pn    printf("\n");

using namespace std;

typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef pair<int,int> ii; 
#define sz(a) int((a).size()) 
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define all(c) (c).begin(),(c).end() 
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end()) 



int main()
{
  int N,M,A[1000][1000],Q,X,x,y;
  scanf("%d %d",&N,&M);
  rep(i,N)
  {
    rep(j,M)
    {
      scanf("%d",&A[i][j]);
    }
  }
  cin>>Q;
  rep(i,Q)
  {
    scanf("%d",&X);
    x=0;y=M-1;
    while(x<N&&y>=0&&A[x][y]!=X)
    {
      if(A[x][y]>X)
        y--;
      else if(A[x][y]<X)
        x++;
    }
    if(y<0||x>=N)
    {
      printf("-1 -1\n");
    }
    else
    {
      printf("%d %d\n",x,y);
    }
  }
  return 0;
}

Second solution

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<cassert>
#include<set>
#include<queue>
#include<map>

using namespace std;

#define vi vector < int >
#define pb push_back
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 1000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define all(x) x.begin(),x.end()

int a[1001][1001];

void find(int val,int n,int m)
{
     int i,j;
     i=0;
     j=m-1;
     while(i<n && j>=0)
     {
        if(a[i][j]==val)
        {
           printf("%d %d\n",i,j);
           return;
        }
        if(a[i][j]>val)
        j--;
        else
        i++;
     }
     printf("-1 -1\n");
}


int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    assert(2<=n && n<=1000);
    assert(2<=m && m<=1000);
    for(i=0;i<n;i++)
    {
       for(j=0;j<m;j++)
       {
           scanf("%d",&a[i][j]);
           assert(-1000000000 <= a[i][j] && a[i][j] <= 1000000000);
       }
    }
    int q;
    scanf("%d",&q);
    assert(2 <= q && q <= 1000);
    while(q--)
    {
              int val;
              scanf("%d",&val);
              assert(-1000000000 <= val && val <= 1000000000);
              find(val,n,m);
    }
    return 0;
}