# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
134578 | 2019-07-23T04:32:49 Z | mohammedehab2002 | XOR (IZhO12_xor) | C++11 | 203 ms | 23416 KB |
#include <iostream> using namespace std; int l,trie[10000000][2],mn[10000000],cn; void insert(int x,int idx) { int cur=0; for (int i=29;i>=0;i--) { bool b=(x&(1<<i)); if (!trie[cur][b]) { trie[cur][b]=++cn; mn[cn]=idx; } cur=trie[cur][b]; mn[cur]=min(mn[cur],idx); } } int get(int x) { int cur=0,ans=1e9; for (int i=29;i>=0;i--) { bool b=(x&(1<<i)),b2=(l&(1<<i)); if (!b2 && trie[cur][!b]) ans=min(ans,mn[trie[cur][!b]]); b^=b2; if (!trie[cur][b]) break; cur=trie[cur][b]; } return ans; } int main() { int n,cum=0,k=-1,idx; scanf("%d%d",&n,&l); l--; for (int i=1;i<=n;i++) { int a; scanf("%d",&a); insert(cum,i-1); cum^=a; int tmp=get(cum); if (i-tmp>k) { k=i-tmp; idx=tmp+1; } } printf("%d %d",idx,k); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 504 KB | Output is correct |
5 | Correct | 9 ms | 1016 KB | Output is correct |
6 | Correct | 11 ms | 1116 KB | Output is correct |
7 | Correct | 12 ms | 1052 KB | Output is correct |
8 | Correct | 13 ms | 1144 KB | Output is correct |
9 | Correct | 58 ms | 11000 KB | Output is correct |
10 | Correct | 55 ms | 11000 KB | Output is correct |
11 | Correct | 57 ms | 11000 KB | Output is correct |
12 | Correct | 56 ms | 11128 KB | Output is correct |
13 | Correct | 74 ms | 11000 KB | Output is correct |
14 | Correct | 60 ms | 11000 KB | Output is correct |
15 | Correct | 61 ms | 10976 KB | Output is correct |
16 | Correct | 64 ms | 11004 KB | Output is correct |
17 | Correct | 197 ms | 23416 KB | Output is correct |
18 | Correct | 158 ms | 23288 KB | Output is correct |
19 | Correct | 191 ms | 23276 KB | Output is correct |
20 | Correct | 203 ms | 23396 KB | Output is correct |