Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #pragma GCC optimize("O3")
- #include "secret.h"
- #define left __left__
- #define right __right__
- using namespace std;
- const int maxn = 1e3 + 10;
- const int maxl = 10;
- int v[maxn], bloco[maxl][maxn], left[maxl][maxn], right[maxl][maxn], n;
- /*int Secret(int a, int b){
- return (a ^ b);
- }
- //*/
- void divide(int ini, int fim, int nl=1){
- if(fim - ini <= 1)
- return;
- int meio = (ini+fim) / 2;
- for(int i=ini;i<=meio;i++)
- bloco[nl][i] = 1;
- for(int i=meio+1;i<=fim;i++)
- bloco[nl][i] = 2;
- left[nl][meio] = v[meio];
- right[nl][meio+1] = v[meio+1];
- for(int i=meio-1;i>=ini;i--)
- if(left[nl][i] == -1) left[nl][i] = Secret(v[i], left[nl][i+1]);
- for(int i=meio+2;i<=fim;i++)
- if(right[nl][i] == -1) right[nl][i] = Secret(right[nl][i-1], v[i]);
- divide(ini, meio, nl+1);
- divide(meio+1, fim, nl+1);
- }
- void Init(int N, int A[]){
- n = N;
- memset(left, -1, sizeof left);
- memset(right, -1, sizeof right);
- for(int i=n;i>=1;i--)
- v[i] = A[i-1];
- divide(1, n);
- }
- inline int qeuri(int l, int r){
- for(int nl=1;;nl++)
- if(bloco[nl][l] != bloco[nl][r])
- return Secret(left[nl][l], right[nl][r]);
- }
- int Query(int l, int r){
- ++l, ++r;
- if(r - l == 1)
- return Secret(v[l], v[r]);
- else if(l == r)
- return v[l];
- return qeuri(l, r);
- }
- #define vet(i) v[i]
- /*int main(){
- int v[] = {1, 2, 3, 4, 5};
- Init(5, v);
- stringstream ss1, ss2;
- for(int i=0;i<n;i++)
- for(int j=i;j<n;j++)
- ss1 << "(" << i+1 << ", " << j+1 << "): " << Query(i, j) << "\n";
- for(int i=0;i<n;i++){
- int resp = vet(i);
- ss2 << "(" << i+1 << ", " << i+1 << "): " << resp << "\n";
- for(int j=i+1;j<n;j++)
- resp = Secret(resp, vet(j)), ss2 << "(" << i+1 << ", " << j+1 << "): " << resp << "\n";
- }
- //cout << bloco[2][1] << " " << bloco[2][3] << "\n";
- cout << (ss1.str() == ss2.str() ? "YES\n" : "NO\n");
- cout << ss1.str() << "\n";
- return 0;
- }//*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement