raghuvanshraj

996.cpp

Aug 2nd, 2021
949
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  25.05.2020 10:50:23 AM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. bool is_square(int x) {
  10.     int l = 0, r = sqrt(x) + 1;
  11.     while (l <= r) {
  12.         int mid = (l + r) / 2;
  13.         if (mid * mid < x) {
  14.             l = mid + 1;
  15.         } else if (mid * mid > x) {
  16.             r = mid - 1;
  17.         } else {
  18.             return true;
  19.         }
  20.     }
  21.  
  22.     return false;
  23. }
  24.  
  25. int _numSquarefulPerms(vector<int> &arr, int idx) {
  26.     int n = arr.size();
  27.     if (idx == n - 1) {
  28.         return 1;
  29.     }
  30.  
  31.     int ans = 0;
  32.     set<int> s;
  33.     for (int j = idx + 1; j <= n - 1; ++j) {
  34.         if (not s.count(arr[j])) {
  35.             int x = arr[idx] + arr[j];
  36.             if (is_square(x)) {
  37.                 swap(arr[idx + 1], arr[j]);
  38.                 ans += _numSquarefulPerms(arr, idx + 1);
  39.                 swap(arr[idx + 1], arr[j]);
  40.             }
  41.  
  42.             s.insert(arr[j]);
  43.         }
  44.     }
  45.  
  46.     return ans;
  47. }
  48.  
  49. int numSquarefulPerms(vector<int> &arr) {
  50.     int n = arr.size();
  51.     int ans = 0;
  52.     set<int> s;
  53.     for (int i = 0; i <= n - 1; ++i) {
  54.         if (not s.count(arr[i])) {
  55.             swap(arr[i], arr[0]);
  56.             ans += _numSquarefulPerms(arr, 0);
  57.             swap(arr[i], arr[0]);
  58.  
  59.             s.insert(arr[i]);
  60.         }
  61.     }
  62.  
  63.     return ans;
  64. }
  65.  
  66. int main(int argc, char const *argv[]) {
  67.     int n;
  68.     cin >> n;
  69.     vector<int> arr(n);
  70.     for (int i = 0; i <= n - 1; ++i) {
  71.         cin >> arr[i];
  72.     }
  73.  
  74.     cout << numSquarefulPerms(arr);
  75.  
  76.     return 0;
  77. }
RAW Paste Data