Question

Problema "pow2-#2239" - pbinfo

Se consideră un șir a[1], a[2],…, a[n] de numere naturale nenule.

Cerința
Să se determine câte perechi de indici (i, j), 1 ≤ i < j ≤ n, există cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n numere naturale nenule, separate prin spații.

Date de ieșire
Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți (i, j) cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Restricții și precizări
2 ≤ n ≤ 100 000
1 ≤ a[i] ≤ 1 000 000 000, pentru orice i = 1..n
Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …


Indicatii :

O soluție de complexitate O(n * log n * log n) care este suficientă pentru a obține punctajul maxim este următoarea. Se ordonează crescător șirul și apoi pentru fiecare a[i] (i = 1..n-1) se caută binar de câte ori apare în secvența a[i + 1 ..n] fiecare valoare strict pozitivă P2-a[i], unde P2 este orice valoare din mulțimea {21, 22, 23, …, 230}.

O soluție de complexitate mai bună utilizează hash-uri.



Am facut solutia de la indicatii si nu functioneaza. Poate cineva sa imi arate solutia de 100 de puncte?

Answer 1

#include <bits/stdc++.h>

#define H 100003

using namespace std;

vector<pair<int,int>> T[H];

int n,i,x[H],p[32],c,v,w,j,h,C;

long long sol;

int main()

{

   cin>>n;

   for(i=1;i<=n;++i)

       cin>>x[i];

   sort(x+1,x+n+1);

   p[0]=1;

   for(i=1;i<=31;++i)

       p[i]=2*p[i-1];

   for(i=n;i;)

   {

       v=x[i];c=0;

       while(x[i]==v)

           --i,++c;

       if(v==(v&(-v)))

           sol+=1LL*c*(c-1)/2;

       for(j=31;;--j)

       {

           w=p[j]-v;

           if(w<=v)

               break;

           h=w%H;

           C=0;

           vector<pair<int,int>>::iterator it;

           for(it=T[h].begin();it!=T[h].end();++it)

               if(it->first==w)

               {

                   C=it->second;

                   break;

               }

           sol+=1LL*c*C;

       }

       h=v%H;

       T[h].push_back(make_pair(v,c));

   }

   cout<<sol;

   return 0;

}