I made correct comparator (I think it is correct) but it gives TLE now I really don't have an idea hot to speed up this , how to mark ndoes faster then map does ,
can somebody suggest me better way to mark them?
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
int len,d,n;
int vis[100100];
int dj[4]={1,1,-1,-1};
int dt[4]={1,-1,1,-1};
inline int abss(const int &a){
if(a<0) return -a;
return a;
}
struct node{
int j,t,js,ts;
node(){}
node(int jane,int tarzan ,int sj,int st)
: j(jane),t(tarzan),js(sj),ts(st) {}
bool operator <(const node &a) const{
return js==a.js?(ts==a.ts?(j==a.j?(t<a.t):j<a.j):ts<a.ts):js<a.js;
}
};
inline bool ok(const int &a, const int &b){
if(a<0||a>=n) return false;
if(b<0||b>=n) return false;
return true;
}
inline bool valid(const int &a,const int &b){
if(abss(vis[a]-vis[b])<=d) return true;
return false;
}
pair<int,int> P[100100];
map<node,bool> M;
queue<node> q;
void solve(){
while(!q.empty()){
node top=q.front();
q.pop();
if(top.j==top.ts&&top.t==top.js) P[len++]=make_pair(top.js,top.ts);
for(int i=0;i<4;++i){
int nj=top.j+dj[i];
int nt=top.t+dt[i];
if(ok(nj,nt)&&valid(nj,nt)){
if(!M[node(nj,nt,top.js,top.ts)]) {
q.push(node(nj,nt,top.js,top.ts));
M[node(nj,nt,top.js,top.ts)]=true;
}
}
}
}
}
int main(){
scanf("%d%d",&n,&d);
for(int i=0;i<n;++i) scanf("%d",&vis[i]);
for(int i=0;i<n-1;++i){
for(int j=i+1;j<n;++j){
if(valid(i,j)){
q.push(node(i,j,i,j));
M[node(i,j,i,j)]=true;
}
}
}
solve();
sort(P,P+len);
for(int i=0;i<len;++i) printf("%d %d\n",P[i].first+1,P[i].second+1);
return 0;
}