fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<iostream>
  3. using namespace std;
  4. #define fre freopen("input-1.txt","r",stdin),freopen("output-1.txt","w",stdout)
  5. #define abs(x) ((x)>0?(x):-(x))
  6. #define M 1000000007
  7. #define lld signed long long int
  8. #define pp pop_back()
  9. #define ps(x) push_back(x)
  10. #define mpa make_pair
  11. #define pii pair<int,int>
  12. #define fi first
  13. #define se second
  14. #define scan(x) scanf("%d",&x)
  15. #define print(x) printf("%d\n",x)
  16. #define scanll(x) scanf("%lld",&x)
  17. #define printll(x) printf("%lld\n",x)
  18. #define boost ios_base::sync_with_stdio(0)
  19. //vector<int> g[2*100000+5];int par[2*100000+5];
  20. lld dp[1048576+5][22];
  21. int freq[1048576+5];
  22. int d[1000000+5];
  23. int main()
  24. {
  25. // freopen("input-6.txt","r",stdin),
  26. //freopen("output-6.txt","w",stdout);
  27. int t;
  28. cin>>t;
  29. while(t--)
  30. {
  31. int n,x,mask;
  32. cin>>n;
  33. for(int i=1;i<=n;++i)
  34. {
  35. scan(d[i]);
  36. freq[d[i]]++;
  37. }
  38. lld ans=0;
  39. for(int mask=0;mask<(1ll<<20);++mask)
  40. {
  41. dp[mask][0]=freq[mask];
  42. if(mask&1)
  43. dp[mask][0]+=freq[mask^1];
  44. for(int p=1;p<=20;++p)
  45. {
  46. dp[mask][p]=dp[mask][p-1];
  47. if(mask&(1<<p))
  48. {
  49. dp[mask][p]+=dp[mask^(1<<p)][p-1];
  50. }
  51. }
  52. }
  53. for(int i=1;i<=n;++i)
  54. {
  55. ans+=dp[(1ll<<20)-1-d[i]][20];
  56. freq[d[i]]=0;
  57. }
  58. cout<<ans<<endl;
  59. }
  60. }
Time limit exceeded #stdin #stdout 5s 191680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nDQiUh
language:
C++ (gcc 8.3)
created:
8 years 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!