Submission #883625

#	Time	Username	Problem	Language	Result	Execution time	Memory
883625		Requiem	XOR (IZhO12_xor)	C++17	0 / 100	859 ms	262144 KiB

xor

#include<bits/stdc++.h>
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF (1<<32)-1
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#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=30;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];
        }
    }
    bool check(int pre,int x){
        p = 1;
        for(it=30;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[4003];
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;
    return min(getminblock(node<<1,l,mid,u,v,pre),
               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<=2002;i++){
       TrieBlock[i].addnum(0);
   }
   int MXBLOCK = (n-1) / block;
   int minblock = 0, idblock;
   for(int i=0;i<=n;i++){
       idblock = i / block;
       minblock = getminblock(1,0,MXBLOCK,0,idblock,prexor[i]);
       if (minblock != INF){
           for(int j=starting[minblock];j<=ending[minblock];j++){
                if ((prexor[i] ^ prexor[j]) >= x){
                   if (maximize(maxlen,i - j)){
                       minpos = j + 1;
                   }
                   else if (maxlen == i - j){
                       minimize(minpos, j + 1);
                   }
               }
           }
       }
       update(1,0,MXBLOCK,idblock,prexor[i]);
   }
   cout<<minpos<<' '<<maxlen<<endl;
}

Compilation message (stderr)

xor.cpp: In function 'int getminblock(int, int, int, int, int, int)':
xor.cpp:5:15: warning: left shift count >= width of type [-Wshift-count-overflow]
    5 | #define INF (1<<32)-1
      |              ~^~~~
xor.cpp:83:21: note: in expansion of macro 'INF'
   83 |         else return INF;
      |                     ^~~
xor.cpp:5:15: warning: left shift count >= width of type [-Wshift-count-overflow]
    5 | #define INF (1<<32)-1
      |              ~^~~~
xor.cpp:85:28: note: in expansion of macro 'INF'
   85 |     if (l>v or r<u) return INF;
      |                            ^~~
xor.cpp: At global scope:
xor.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main()
      | ^~~~
xor.cpp: In function 'int main()':
xor.cpp:5:15: warning: left shift count >= width of type [-Wshift-count-overflow]
    5 | #define INF (1<<32)-1
      |              ~^~~~
xor.cpp:114:24: note: in expansion of macro 'INF'
  114 |        if (minblock != INF){
      |                        ^~~
xor.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100