| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1101688 | thefless | XOR (IZhO12_xor) | C++17 | 95 ms | 120768 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define Times (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define base 31
#define sz(x) (int)(x).size()
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); freopen(name".bug", "w", stderr); }
#define task "name"
#define tsk ""
const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int MOD2 = 1e9 + 696969;
const int N = 250000 + 3;
const int BASE = 10;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
int n , x;
int a[N];
struct TRIE{
struct NODE{
int cnt, idx;
int child[2];
NODE(){cnt = child[0] = child[1] = 0;idx = oo;}
}t[N * 30];
int cnt;
void add(int s, int vt){
int root = 0;
for(int i = 30 ; i >= 0 ; i--){
int id = BIT(s , i);
if(!t[root].child[id]) t[root].child[id] = ++cnt;
root = t[root].child[id];
t[root].cnt++;
minimize(t[root].idx , vt);
}
}
int dfs(int root , int s , int dept){
if(root == 0 && dept != 30) return oo;
if(dept < 0) return t[root].idx;
int l = t[root].child[0];
int r = t[root].child[1];
if(BIT(s , dept)) swap(l , r);
if(BIT(x , dept)){
int res = dfs(r , s , dept - 1);
return res;
}
int res = dfs(l , s , dept - 1);
return min(t[r].idx , res);
}
}trie;
void Solve(){
cin >> n >> x;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
trie.add(0 , 0);
int pre = 0 , siz = 0 , st = 0;
for(int i = 1 ; i <= n ; i++){
pre ^= a[i];
int w = trie.dfs(0 , pre , 30);
if(w != oo){
if(maximize(siz , i - w)) st = w + 1;
}
trie.add(pre , i);
}
cout << st << ' ' << siz;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
file(task);
file(tsk);
int T = 1;
// cin >> T;
while(T--)
{
Solve();
}
cerr << "Time elapsed: " << Times << " s.\n";
return 0;
}
// author: thefless
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||