답안 #446571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446571	2021-07-22T13:05:42 Z	minaie_mehrzad	XOR (IZhO12_xor)	C++14	100 / 100	492 ms	153796 KB

xor

#include <bits/stdc++.h>
using namespace std;

const int maxn = 25e4 + 10, lg = 31;
int n, a[maxn], z;

struct node {
    node *rc, *lc;
    int mn;
    
    node () {
        lc = nullptr;
        rc = nullptr;
        mn = 1e9;
    }
    
    node * getChild(int x) {
        if (x) {
            if (rc == nullptr) rc = new node();
            return rc;
        } else {
            if (lc == nullptr) lc = new node();
            return lc;
        }
    }
};

struct Trie {
    node *root;
    
    Trie () {
        root = new node();
    }
    
    void add(int x, int y) {
        node * cur = root;
        for (int i = lg; i >= 0; i--) {
            cur = cur->getChild(!!((1 << i) & x));
            cur->mn = min(cur->mn, y);
        }
    }
} T;

int solve(int x) {
    int ans = 1e9;
    node *cur = T.root;
    
    for (int i = lg; i >= 0; i--) {
        int c = !!((1 << i) & x), d = !!((1 << i) & z);
        
        if (!d) {
            ans = min(ans, cur->getChild(!c)->mn);
        }
        
        cur = cur->getChild(c ^ d);
    }
    
    ans = min(ans, cur->mn);
    return ans;
}

int main () {
    ios_base::sync_with_stdio(false);
    
    cin >> n >> z;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i-1];
        T.add(a[i], i);
    }
    
    int ans = 0, ind = 0;
    
    for (int i = 1; i <= n; i++) {
        if (a[i] >= z && ans < i) {
            ans = i;
            ind = 1;
        }
        
        int r = solve(a[i]);

        if (ans < i - r) {
            ans = i - r;
            ind = r + 1;
        }
    }
    
    cout << ind << " " << ans;
    
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	2 ms	844 KB	Output is correct
5	Correct	14 ms	3252 KB	Output is correct
6	Correct	17 ms	3840 KB	Output is correct
7	Correct	18 ms	3612 KB	Output is correct
8	Correct	19 ms	3788 KB	Output is correct
9	Correct	187 ms	64580 KB	Output is correct
10	Correct	172 ms	66500 KB	Output is correct
11	Correct	170 ms	62712 KB	Output is correct
12	Correct	166 ms	62276 KB	Output is correct
13	Correct	157 ms	59860 KB	Output is correct
14	Correct	163 ms	60780 KB	Output is correct
15	Correct	178 ms	71576 KB	Output is correct
16	Correct	161 ms	60484 KB	Output is correct
17	Correct	442 ms	146136 KB	Output is correct
18	Correct	440 ms	144420 KB	Output is correct
19	Correct	492 ms	153796 KB	Output is correct
20	Correct	413 ms	131392 KB	Output is correct