Guest User

Untitled

a guest
Oct 18th, 2019
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define ll long long
  4. #define ld long double
  5. #define pb push_back
  6. #define ff first
  7. #define ss second
  8. #define sp fixed<<setprecision
  9. #define pii pair<int,int>
  10. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  11. #define bp __builtin_popcount
  12. #define int ll
  13. using namespace std;
  14. ll M = (1e9)+7;
  15.  
  16. signed main()
  17. {
  18. FAST
  19. int tc=1;
  20. cin>>tc;
  21. while(tc--)
  22. {
  23. int n,tot=0,len;
  24. cin>>n;
  25. pii a[n];
  26. set<pii> s[31];
  27. len=n;
  28. vector<int> ans;
  29. set<pii> r;
  30. for(int i=0;i<n;i++)
  31. {
  32. cin>>a[i].ff,a[i].ss=i+1;
  33. if(!a[i].ff)
  34. {
  35. len--;
  36. ans.pb(i+1);
  37. }
  38. else
  39. {
  40. r.insert(a[i]);
  41. }
  42. tot|=a[i].ff;
  43. int x=a[i].ff;
  44. for(int j=0;j<31;j++)
  45. {
  46. if((1LL<<j) & x)s[j].insert(a[i]);
  47. }
  48. }
  49. int fa=tot;
  50. fa+=(n-len)*tot;
  51. for(int i=0;i<len;i++)
  52. {
  53. set<pii> nr;
  54. for(int j=0;j<31;j++)
  55. {
  56. if(s[j].size()==1)nr.insert(*s[j].begin());
  57. }
  58. pii rem;
  59. int fl=0;
  60. for(auto it:r)
  61. {
  62. if(nr.find(it)==nr.end()){fl=1;rem=it;break;}
  63. }
  64. if(!fl)
  65. {
  66. int mi = 1e10;
  67. for(auto it:nr)
  68. {
  69. int num = it.ff,red=0;
  70. for(int j=0;j<31;j++)
  71. {
  72. if(((1LL<<j) & num) && s[j].size()==1)red+=(1LL<<j);
  73. }
  74. if(red<mi)
  75. {
  76. mi = red;
  77. rem = it;
  78. }
  79. }
  80. }
  81. ans.pb(rem.ss);
  82. r.erase(rem);
  83. for(int j=0;j<31;j++)
  84. {
  85. if(rem.ff & (1LL<<j))
  86. {
  87. s[j].erase(s[j].find(rem));
  88. if(s[j].size()==0)tot^=(1LL<<j);
  89. }
  90. }
  91. fa+=tot;
  92. }
  93. cout<<fa<<endl;
  94. for(int i=0;i<n;i++)cout<<ans[i]<<" ";
  95. cout<<endl;
  96. }
  97. return 0;
  98. }
Add Comment
Please, Sign In to add comment