Submission #883638

#	Time	Username	Problem	Language	Result	Execution time	Memory
883638		Requiem	XOR (IZhO12_xor)	C++17	0 / 100	2065 ms	238848 KiB

xor

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 2147483646
#define endl "\n"
#define TASKNAME "Xor"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 250009;
const int block = 501;
int n,k;
int a[MAXN],prexor[MAXN];
struct TrieNode{
    int child[2];
    TrieNode(){
       memset(child,0,sizeof(child));
    }
};
struct Trie{
    vector<TrieNode> Trie = {TrieNode(),TrieNode()};
    int bitpre, bit, it, p, pw2;
    void addnum(int x){
        p = 1;
        for(it=29;it>=0;it--){
            bit = (x>>it)&1;
            if (Trie[p].child[bit] == 0){
                Trie[p].child[bit] = Trie.size();
                Trie.pb(TrieNode());
            }
            p = Trie[p].child[bit];
        }
    }
    inline bool check(int pre,int x){
        p = 1;
        for(it=29;it>=0;it--){
            bitpre = (pre>>it)&1;
            pw2 = (1LL<<it);
            if (Trie[p].child[!bitpre]){
                if (x >= pw2 * 2) return false;
                x -= pw2;
                if (x <= 0) return true;

                p = Trie[p].child[!bitpre];
            }
            else{
                p = Trie[p].child[bitpre];
            }
        }
        return (x <= 0);
    }
};
Trie TrieBlock[2003];
int starting[MAXN],ending[MAXN];
int maxlen, minpos,x;
void update(int node,int l,int r,int pos,int pre){
    TrieBlock[node].addnum(pre);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (pos <= mid) update(node<<1,l,mid,pos,pre);
    else update(node<<1|1,mid+1,r,pos,pre);
}
int getminblock(int node,int l,int r,int u,int v,int pre){
    int mid = (l+r)>>1;
    if (l>=u and r<=v){
        if (l==r) return l;
        if (TrieBlock[node<<1].check(pre,x)){
            return getminblock(node<<1,l,mid,u,v,pre);
        }
        else if (TrieBlock[node<<1|1].check(pre,x)){
            return getminblock(node<<1|1,mid+1,r,u,v,pre);
        }
        else return INF;
    }
    if (l>v or r<u) return INF;
    int g1 = getminblock(node<<1,l,mid,u,v,pre);
    if (g1 != INF) return g1;
    else return getminblock(node<<1|1,mid+1,r,u,v,pre);
}
main()
{
    fast;
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
   }
   cin>>n>>x;
   for(int i=1;i<=n;i++){
       cin>>a[i];
       prexor[i] = prexor[i-1] ^ a[i];
   }
   for(int i=0;i<n;i++){
       starting[i/block] = (starting[i/block] == -1) ? i : starting[i/block];
       ending[i/block] = i;
   }
   for(int i=0;i<=2000;i++){
       TrieBlock[i].addnum(0);
   }
   int MXBLOCK = (n-1) / block;
   int minblock = 0, idblock,i,j;
   for(i=0;i<=n;i++){
       idblock = i / block;
       minblock = getminblock(1,0,MXBLOCK,0,idblock,prexor[i]);
       if (minblock != INF){
           for(j=starting[minblock]; i - j >= maxlen and j<=min(i,ending[minblock]);j++){
                if ((prexor[i] ^ prexor[j]) >= x){
                   if (maximize(maxlen,i - j)){
                       minpos = j + 1;
                       j = ending[minblock]+1;
                   }
                   else if (maxlen == i - j){
                       minimize(minpos, j + 1);
                       j = ending[minblock]+1;
                   }
               }
           }
       }
       update(1,0,MXBLOCK,idblock,prexor[i]);
   }
   cout<<minpos<<' '<<maxlen<<endl;
}

Compilation message (stderr)

xor.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main()
      | ^~~~
xor.cpp: In function 'int main()':
xor.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100