Advertisement
FreakSkipper

Encontre a diferença

Sep 3rd, 2020
1,453
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. // E. Encontre a diferença
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. bool ordena(pair<int, int> a, pair<int, int> b) {
  7.     return a.second < b.second;
  8. }
  9.  
  10. int main() {
  11.     int n, k;
  12.     vector<pair<int, int>> num;
  13.     cin >> n >> k;
  14.  
  15.     for (int i = 0; i < n; i++) {
  16.         int aux;
  17.         cin >> aux;
  18.         num.push_back(make_pair(i, aux));
  19.     }
  20.  
  21.     sort(num.begin(), num.end(), ordena);
  22.  
  23.     bool founded = false;
  24.     for (int i = 0; i < n && !founded; i++) {
  25.         int target = num[i].second - k;
  26.         int begin = 0;
  27.         int end = n - 1;
  28.  
  29.         int found_idx = -1;
  30.  
  31.         while (begin < end) {
  32.             int middle = (end + begin) / 2;
  33.  
  34.             if (num[middle].second == target && num[middle].first != num[i].first) {
  35.                 found_idx = num[middle].first;
  36.                 break;
  37.             } else {
  38.                 if (target > num[middle].second) {
  39.                     begin = middle + 1;
  40.                 } else {
  41.                     end = middle - 1;
  42.                 }
  43.             }
  44.         }
  45.  
  46.         if (found_idx != -1) {
  47.             cout << "Sim" << endl;
  48.             cout << num[i].first + 1 << ' ' << found_idx + 1 << endl;
  49.             founded = true;
  50.         }
  51.     }
  52.  
  53.     if (!founded) {
  54.         cout << "Nao" << endl;
  55.     }
  56.  
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement