oj.uz

Submission #966125

# Submission time Handle Problem Language Result Execution time Memory
966125 2024-04-19T12:08:46 Z noyancanturk XOR (IZhO12_xor) C++17
100 / 100
 123 ms 178520 KB 
#include "bits/stdc++.h"
using namespace std;
    
//#define int int64_t
#define pb push_back
    
const int lim=1.5e7+500;
const int mod=1e9+7;

using pii=pair<int,int>;

int n,k;

struct{
    
    struct node{
        int c[2];
        int val=INT_MAX;
    };

    node nds[lim];
    int cnd=2;

    #define now nds[cur]

    void insert(int x,int k){
        int cur=1;
        for(int i=29;0<=i;i--){
            if(!now.c[(x>>i)&1]){
                now.c[(x>>i)&1]=cnd++;
            }
            cur=now.c[(x>>i)&1];
            if(k<now.val)now.val=k;
        }
    }

    int findval(int x){
        int ans=INT_MAX,cur=1;
        for(int i=29;0<=i;i--){
            bool bt=(x>>i)&1;
            if((k>>i)&1){
                if(!now.c[!bt]){
                    return ans;
                }
                cur=now.c[!bt];
            }else{
                if(now.c[!bt]&&nds[now.c[!bt]].val<ans){
                    ans=nds[now.c[!bt]].val;
                }
                if(!now.c[bt]){
                    return ans;
                }
                cur=now.c[bt];
            }
        }
        return min(ans,now.val);
    }

}trie;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin); freopen(".out","w",stdout);
#endif
    cin>>n>>k;
    int past=0;
    int64_t l=0,r=-1,sz=0;
    trie.insert(0,-1);
    for(int i=0;i<n;i++){
        int tem;
        cin>>tem;
        past^=tem;
        int ll=trie.findval(past);
        if(ll!=INT_MAX&&sz<i-ll){
            l=ll+1;
            sz=i-ll;
        }
        trie.insert(past,i);
    }
    cout<<l+1<<" "<<sz<<"\n";
}

Compilation message

xor.cpp: In function 'int main()':
xor.cpp:68:17: warning: unused variable 'r' [-Wunused-variable]
   68 |     int64_t l=0,r=-1,sz=0;
      |                 ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 176464 KB Output is correct
2 Correct 46 ms 176468 KB Output is correct
3 Correct 44 ms 176464 KB Output is correct
4 Correct 46 ms 176464 KB Output is correct
5 Correct 48 ms 176468 KB Output is correct
6 Correct 49 ms 176508 KB Output is correct
7 Correct 51 ms 176588 KB Output is correct
8 Correct 49 ms 176580 KB Output is correct
9 Correct 65 ms 177092 KB Output is correct
10 Correct 72 ms 177236 KB Output is correct
11 Correct 62 ms 177232 KB Output is correct
12 Correct 63 ms 177232 KB Output is correct
13 Correct 62 ms 177320 KB Output is correct
14 Correct 64 ms 177116 KB Output is correct
15 Correct 64 ms 177324 KB Output is correct
16 Correct 64 ms 177088 KB Output is correct
17 Correct 102 ms 178356 KB Output is correct
18 Correct 105 ms 178372 KB Output is correct
19 Correct 100 ms 178340 KB Output is correct
20 Correct 123 ms 178520 KB Output is correct