| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 883616 |
2023-12-05T14:15:19 Z |
Requiem |
XOR (IZhO12_xor) |
C++17 |
|
2000 ms |
219800 KB |
#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[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;
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<=2000;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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
3 ms |
7016 KB |
Output is correct |
| 5 |
Correct |
97 ms |
18992 KB |
Output is correct |
| 6 |
Correct |
183 ms |
22308 KB |
Output is correct |
| 7 |
Correct |
198 ms |
22792 KB |
Output is correct |
| 8 |
Correct |
242 ms |
25268 KB |
Output is correct |
| 9 |
Correct |
1680 ms |
216724 KB |
Output is correct |
| 10 |
Correct |
1646 ms |
219800 KB |
Output is correct |
| 11 |
Correct |
1702 ms |
215280 KB |
Output is correct |
| 12 |
Correct |
1764 ms |
217508 KB |
Output is correct |
| 13 |
Correct |
1698 ms |
215644 KB |
Output is correct |
| 14 |
Correct |
1663 ms |
216148 KB |
Output is correct |
| 15 |
Correct |
1708 ms |
215148 KB |
Output is correct |
| 16 |
Correct |
1661 ms |
217116 KB |
Output is correct |
| 17 |
Execution timed out |
2053 ms |
218060 KB |
Time limit exceeded |
| 18 |
Halted |
0 ms |
0 KB |
- |
