Advertisement
Kali_prasad

triplet with sum k (using hash map)

Apr 5th, 2022
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef pair<string,int> psi;
  10. typedef map<int,int> mii;
  11. typedef map<long long,long long> mll;
  12. typedef map<string,int> msi;
  13. typedef map<char,int> mci;
  14. typedef vector<int> vi;
  15. typedef vector<string> vs;
  16. typedef vector<char> vc;
  17. typedef vector<ll> vll;
  18. typedef vector<vector<int>> vvi;
  19. typedef vector<vector<string>> vvs;
  20. typedef vector<vector<ll>> vvll;
  21.  
  22. #define FOR(i, a, b) for (auto i=a; i<=(b); i++)
  23. #define FORd(i,b,a) for (int i =b; i >= a; i--)
  24. #define sz(x) (int)(x).size()
  25. #define mp make_pair
  26. #define pb push_back
  27. #define f first
  28. #define s second
  29. #define ins insert
  30.  
  31. const int MOD = 1000000007;
  32. //type functions here
  33. //using map
  34. bool check(mll &m,vi &v,int k)
  35. {
  36.     int size=(v.size()-3);  
  37.     FOR(i,0,size)
  38.     {
  39.         ll temp=k-v[i];
  40.         m[v[i]]--;
  41.        
  42.      
  43.         FOR(j,i+1,size+1)
  44.         {
  45.          ll temp2=temp-v[j];
  46.          m[v[j]]--;
  47.          if(m[temp2]>0) return true;
  48.         }
  49.         FOR(j,i+1,size+1)
  50.         {
  51.        
  52.          m[v[j]]++;
  53.          
  54.         }
  55.     }
  56.     return false;
  57. }
  58.  
  59. int main() {
  60.      ios_base::sync_with_stdio(false);
  61.     cin.tie(NULL);
  62.     int tc=1;
  63.     cin>>tc;
  64.     FOR(j,1,tc){
  65.     vi v;//={5, 5 ,1};
  66.     int k,n;
  67.     cin>>n>>k;
  68.     FOR(i,1,n)
  69.     {
  70.         int temp;
  71.         cin>>temp;
  72.         v.pb(temp);
  73.     }
  74.     mll m;
  75.    // ll min=*min_element(v.begin(),v.end());//am i audibl
  76.  
  77.     for(auto x:v)
  78.     m[x]++;
  79.    
  80.     bool c=check(m,v,k);
  81.     if(c) cout<<"true"<<endl;
  82.     else cout<<"false"<<endl;
  83.    
  84.     }
  85.     return 0;
  86. }
  87.  
  88.  
  89.  
  90.  
  91.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement