Guest User

ANDROUND

a guest
Jul 28th, 2017
464
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.90 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define mod 1000000007
  4. #define mp make_pair
  5. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define pb push_back
  7. #define endl '\n'
  8. #define pii pair<int ,int >
  9. #define lc 2*x+1
  10. #define rc 2*x+2
  11. #define all(v) v.begin(),v.end()
  12. ll poww(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  13. using namespace std;
  14.  
  15. ll int a[20005],ans[20005],tree[100005];
  16.  
  17. void build(int l,int r,int x){
  18.  
  19. if(l==r){
  20. tree[x]=a[l];
  21. return;
  22. }
  23. int mid=(l+r)/2;
  24. build(l,mid,lc);
  25. build(mid+1,r,rc);
  26. tree[x]=tree[lc]&tree[rc];
  27. }
  28.  
  29. ll query(int ql,int qr,int l,int r,int x){
  30.  
  31. if(l>r||ql>r||l>qr)
  32. return 8589934591;
  33. if(ql<=l&&qr>=r)
  34. return tree[x];
  35. int mid=(l+r)/2;
  36. ll ans;
  37. ans=query(ql,qr,l,mid,lc);
  38. ans&=query(ql,qr,mid+1,r,rc);
  39. return ans;
  40. }
  41.  
  42. int main()
  43. {
  44. fast;
  45. //freopen("input.txt", "r+", stdin);
  46. //freopen("output.txt", "w+", stdout);
  47.  
  48. ll int t,i,j,k,n;
  49.  
  50. cin>>t;
  51. while(t--){
  52.  
  53. cin>>n>>k;
  54. for(i=0;i<n;++i){
  55. cin>>a[i];
  56. if(!i)
  57. j=a[i];
  58. else j&=a[i];
  59. }
  60. build(0,n-1,0);
  61. for(i=0;i<n;++i){
  62. if(k>n/2)
  63. ans[i]=j;
  64. else{
  65. if(i+k>=n){
  66. ans[i]=query(i,n-1,0,n-1,0);
  67. ans[i]&=query(0,(i+k)%n,0,n-1,0);
  68. }
  69. else
  70. ans[i]=query(i,(i+k),0,n-1,0);
  71. if(i-k<0){
  72. ans[i]&=query(0,i,0,n-1,0);
  73. ans[i]&=query(n-k+i,n-1,0,n-1,0);
  74. }
  75. else
  76. ans[i]&=query(i-k,i,0,n-1,0);
  77.  
  78. }
  79. cout<<ans[i]<<" ";
  80. }
  81. cout<<endl;
  82. }
  83.  
  84. return 0;
  85. }
Add Comment
Please, Sign In to add comment