oj.uz

답안 #966142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
966142 2024-04-19T12:22:32 Z dosts XOR (IZhO12_xor) C++17
100 / 100
 106 ms 24716 KB 
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+100,inf = INT_MAX,MOD = 1e9+7,LIM = 3e7+1;

int curnode = 1;
struct Node {
    int c[2],mx;
};

Node nds[LIM];
int walk(Node* cur, int x,int k,int bit = 29) { 
    if (bit == -1) return k?0:cur->mx;
    //x ile xor layınca en az k gelmesi lzm
    if (k & (1<<bit)) {
        int go = !(x&(1<<bit));
        if (cur->c[go]) return walk(nds+cur->c[go],x,k^(1<<bit),bit-1);
        else return 0;
    }
    else {
        int go = !(x&(1<<bit));
        int ans = 0;
        if (cur->c[go]) ans = max(ans,nds[cur->c[go]].mx);
        ans = max(ans,walk(nds+cur->c[!go],x,k,bit-1));
        return ans;
    }
}
 
void insert(int x,int p) {
    Node* cur = nds+1;
    for (int i=29;i>=-1;i--) {
        cur->mx = max(cur->mx,p);
        if (i > -1) {
            bool go = !!(x&(1<<i));
            if (!cur->c[go]) cur->c[go] = ++curnode;
            cur = nds+cur->c[go];
        }
    }
}

 



void solve() {
    int n,x;
    cin >> n >> x;
    vi a(n+1),p(n+1,0);
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=n;i++) p[i] = p[i-1]^a[i];
    int ans = 0,start = 0;
    for (int i=n;i>=1;i--) {
        insert(p[i],i);
        int xx = walk(nds+1,p[i-1],x);
        if (xx-i+1 >= ans) {
            ans = xx-i+1;
            start = i;
        }
    }
    cout << start sp ans << endl;
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 7 ms 1116 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 8 ms 1380 KB Output is correct
8 Correct 8 ms 1452 KB Output is correct
9 Correct 29 ms 11856 KB Output is correct
10 Correct 33 ms 11736 KB Output is correct
11 Correct 29 ms 11860 KB Output is correct
12 Correct 32 ms 11792 KB Output is correct
13 Correct 28 ms 11860 KB Output is correct
14 Correct 29 ms 11872 KB Output is correct
15 Correct 28 ms 11860 KB Output is correct
16 Correct 28 ms 11808 KB Output is correct
17 Correct 82 ms 24584 KB Output is correct
18 Correct 84 ms 24716 KB Output is correct
19 Correct 106 ms 24688 KB Output is correct
20 Correct 85 ms 24572 KB Output is correct