Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2019
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3")
  3. #include "secret.h"
  4. #define left __left__
  5. #define right __right__
  6.  
  7. using namespace std;
  8. const int maxn = 1e3 + 10;
  9. const int maxl = 10;
  10.  
  11. int v[maxn], bloco[maxl][maxn], left[maxl][maxn], right[maxl][maxn], n;
  12.  
  13. /*int Secret(int a, int b){
  14. return (a ^ b);
  15. }
  16. //*/
  17.  
  18. void divide(int ini, int fim, int nl=1){
  19. if(fim - ini <= 1)
  20. return;
  21.  
  22. int meio = (ini+fim) / 2;
  23.  
  24. for(int i=ini;i<=meio;i++)
  25. bloco[nl][i] = 1;
  26. for(int i=meio+1;i<=fim;i++)
  27. bloco[nl][i] = 2;
  28.  
  29.  
  30. left[nl][meio] = v[meio];
  31. right[nl][meio+1] = v[meio+1];
  32.  
  33. for(int i=meio-1;i>=ini;i--)
  34. if(left[nl][i] == -1) left[nl][i] = Secret(v[i], left[nl][i+1]);
  35.  
  36. for(int i=meio+2;i<=fim;i++)
  37. if(right[nl][i] == -1) right[nl][i] = Secret(right[nl][i-1], v[i]);
  38.  
  39.  
  40. divide(ini, meio, nl+1);
  41. divide(meio+1, fim, nl+1);
  42. }
  43.  
  44. void Init(int N, int A[]){
  45. n = N;
  46.  
  47. memset(left, -1, sizeof left);
  48. memset(right, -1, sizeof right);
  49.  
  50. for(int i=n;i>=1;i--)
  51. v[i] = A[i-1];
  52.  
  53. divide(1, n);
  54. }
  55.  
  56. inline int qeuri(int l, int r){
  57. for(int nl=1;;nl++)
  58. if(bloco[nl][l] != bloco[nl][r])
  59. return Secret(left[nl][l], right[nl][r]);
  60. }
  61.  
  62. int Query(int l, int r){
  63. ++l, ++r;
  64. if(r - l == 1)
  65. return Secret(v[l], v[r]);
  66. else if(l == r)
  67. return v[l];
  68.  
  69. return qeuri(l, r);
  70. }
  71.  
  72. #define vet(i) v[i]
  73. /*int main(){
  74. int v[] = {1, 2, 3, 4, 5};
  75. Init(5, v);
  76.  
  77. stringstream ss1, ss2;
  78. for(int i=0;i<n;i++)
  79. for(int j=i;j<n;j++)
  80. ss1 << "(" << i+1 << ", " << j+1 << "): " << Query(i, j) << "\n";
  81.  
  82. for(int i=0;i<n;i++){
  83. int resp = vet(i);
  84. ss2 << "(" << i+1 << ", " << i+1 << "): " << resp << "\n";
  85. for(int j=i+1;j<n;j++)
  86. resp = Secret(resp, vet(j)), ss2 << "(" << i+1 << ", " << j+1 << "): " << resp << "\n";
  87.  
  88. }
  89.  
  90. //cout << bloco[2][1] << " " << bloco[2][3] << "\n";
  91. cout << (ss1.str() == ss2.str() ? "YES\n" : "NO\n");
  92. cout << ss1.str() << "\n";
  93. return 0;
  94. }//*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement