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;
}