fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. long long int arr[1000002],d;
  4. map<pair<int,int>,int> m2;
  5. int n,a,b;
  6. bool valid(int x,int y)
  7. {
  8.     if(x<n && x>-1 && y>-1 && y<n) return true;
  9.     return false;
  10. }
  11. bool possible(int i,int j)
  12. {
  13.     map<pair<int,int>,int> vis;
  14.     int ini_upp=i,ini_down=j,upp,down;
  15.     queue<pair<int,int>> q;
  16.     q.push(make_pair(ini_upp,ini_down));
  17.     int tv1=m2[make_pair(ini_upp,ini_down)];
  18.     if(tv1){
  19.         // cout<<"aaya jaaha";
  20.         if(tv1==1) return true;
  21.         return false;
  22.     }
  23.     while ((q.size()))
  24.     {
  25.         upp=q.front().first;
  26.         down=q.front().second;
  27.         q.pop();
  28.         if(abs(arr[upp]-arr[down])<=d)
  29.         {
  30.             if (!vis[make_pair(upp,down)]){ 
  31.             vis[make_pair(upp, down)] = 1;
  32.             if(upp==ini_down && down==ini_upp){ 
  33.             m2[make_pair(ini_upp,ini_down)]=1;
  34.             return true;
  35.             }
  36.             if(valid(upp+1,down-1)) q.push(make_pair(upp+1,down-1));
  37.             if(valid(upp+1,down+1)) q.push(make_pair(upp+1,down+1));
  38.             if(valid(upp-1,down-1)) q.push(make_pair(upp-1,down-1));
  39.             if(valid(upp-1,down+1)) q.push(make_pair(upp-1,down+1));
  40.             }
  41.         }
  42.     }
  43.     m2[make_pair(ini_upp, ini_down)] = -1;
  44.     return false;
  45. }
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     cin>>n>>d;
  51.     for (int i = 0; i < n; i++)
  52.     {
  53.         cin>>arr[i];
  54.     }
  55.     for (int i = 0; i < n; i++)
  56.     {
  57.         for (int j = i+1; j < n; j++)
  58.         {
  59.             if(possible(i,j)) cout<<i+1<<" "<<j+1<<"\n";
  60.         }
  61.     }
  62. }
Success #stdin #stdout 0s 4540KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/toh5I9
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!