Submission #883615

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
883615	2023-12-05T14:01:42 Z	Requiem	XOR (IZhO12_xor)	C++17	0 / 100	2000 ms	22024 KB

xor

#include<bits/stdc++.h>
#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 1e18
#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 = 500;
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()};
    void addnum(int x){
        int p = 1;
        for(int i=30;i>=0;i--){
            int bit = (x>>i)&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){
        int p = 1, mx = 0;
        for(int i=30;i>=0;i--){
            int bitpre = (pre>>i)&1;
            int pw2 = (1LL<<i);
            if (Trie[p].child[!bitpre]){
                mx = mx + pw2;
                if (mx >= x) return true;
                p = Trie[p].child[!bitpre];
            }
            else{
                p = Trie[p].child[bitpre];
            }
        }
        return false;
    }
};
Trie TrieBlock[503];
int starting[MAXN],ending[MAXN];
int maxlen, minpos,x;
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;
   }
   int minblock = 0, idblock;
   for(int i=0;i<=n;i++){
       idblock = i / block;
       minblock = idblock;
       for(int b=0;b<idblock;b++){
           if (TrieBlock[b].check(prexor[i],x)){
               minblock = b;
               break;
           }
       }
       if (minblock != idblock){
           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);
                   }
               }
           }
       }
       else{
           for(int j=starting[idblock];j<i;j++){
//                cout<<i<<' '<<j<<' '<<(prexor[i] ^ prexor[j])<<
//                endl;
               if ((prexor[i] ^ prexor[j]) >= x){
                   if (maximize(maxlen,i - j)){
                       minpos = j + 1;
                   }
                   else if (maxlen == i - j){
                       minimize(minpos, j + 1);
                   }
               }
           }
       }
       TrieBlock[idblock].addnum(prexor[i]);
   }
   cout<<minpos<<' '<<maxlen<<endl;
}

Compilation message

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4952 KB	Output is correct
4	Correct	2 ms	4700 KB	Output is correct
5	Correct	216 ms	7436 KB	Output is correct
6	Correct	349 ms	8276 KB	Output is correct
7	Correct	370 ms	8384 KB	Output is correct
8	Correct	465 ms	8788 KB	Output is correct
9	Execution timed out	2013 ms	22024 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-