fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <bitset>
  5. #include<bits/stdc++.h>
  6.  
  7. const int MAX_PALINDROME = (1 << 15);
  8.  
  9. std::vector<int> generatePalindromes() {
  10.     std::vector<int> palindromes;
  11.     std::unordered_map<int, int> freq;
  12.  
  13.     for (int i = 0; i < MAX_PALINDROME; i++) {
  14.         std::bitset<15> bits(i);
  15.         std::string str = bits.to_string();
  16.         std::reverse(str.begin(), str.end());
  17.         int palindrome = std::stoi(str, nullptr, 2);
  18.         palindromes.push_back(palindrome);
  19.         freq[palindrome]++;
  20.     }
  21.  
  22.     return palindromes;
  23. }
  24.  
  25. int countPalindromeXORPairs(const std::vector<int>& A, const std::vector<int>& palindromes) {
  26.     int count = 0;
  27.     std::unordered_map<int, int> freq;
  28.  
  29.     for (int num : A) {
  30.         for (int palindrome : palindromes) {
  31.             int XOR = num ^ palindrome;
  32.             if (freq.count(XOR)) {
  33.                 count += freq[XOR];
  34.             }
  35.         }
  36.         freq[num]++;
  37.     }
  38.  
  39.     return count;
  40. }
  41.  
  42. int main() {
  43.     int T;
  44.     std::cin >> T;
  45.  
  46.     std::vector<int> palindromes = generatePalindromes();
  47.  
  48.     while (T--) {
  49.         int N;
  50.         std::cin >> N;
  51.  
  52.         std::vector<int> A(N);
  53.         for (int i = 0; i < N; i++) {
  54.             std::cin >> A[i];
  55.         }
  56.  
  57.         int pairs = countPalindromeXORPairs(A, palindromes);
  58.         std::cout << pairs << std::endl;
  59.     }
  60.  
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.02s 5388KB
comments (?)
stdin
copy 
2
4
13 27 12 26
3
2 2 2
stdout
copy 
6
3
https://ideone.com/vVd5xI
language:
C++ (gcc 8.3)
created:
324 days 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!