제출 #883616

#제출 시각아이디문제언어결과실행 시간메모리
883616RequiemXOR (IZhO12_xor)C++17
0 / 100
2053 ms219800 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...