Submission #2139602


Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(kbrni,n)cout<<" "<<a[kbrni];cout<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define svecp(v) cout<<#v<<":";each(kbrni,v)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

class BinaryTrie {
public:
	struct Node {
		Node *next[2];
		int sub;
		Node() : sub(0) { next[0] = next[1] = nullptr; }
	};
	Node* root;
    static const int MAX_BIT = 21;
	BinaryTrie(){
		root = new Node();
	}
	//Trie木にxを加える
	void add(int x) {
		Node *curr = root;
		rrep(i,MAX_BIT){
			int y = x >> i & 1;
			if (!curr->next[y]) {
				curr->next[y] = new Node();
			}
			curr->sub++;
			curr = curr->next[y];
		}
		curr->sub++;
	}
    //何らかのクエリ
	int query(Node *curr,const int a,int nw,int d){
        if(d == 0){
            return nw;
        }
		// 対応するビットがd-1であることに注意
		if((a >> (d-1)) & 1){
            if(curr->next[0]){
                return query(curr->next[0],a,nw,d-1);
            }else{
                return query(curr->next[1],a,nw^((1 << (d-1))),d-1);
            }
		}else{
            if(curr->next[1]){
                return query(curr->next[1],a,nw^((1 << (d-1))),d-1);
            }else{
                return query(curr->next[0],a,nw,d-1);
            }
        }
	}
    int query(const int a){
        return query(root,a,a,MAX_BIT);
    }
};

map<int,int> mp;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vi a(n);
    rep(i,n){
        cin >> a[i];
    }
    BinaryTrie bt;
    int nw = 0;
    bt.add(nw);
    int ans = -1;
    mp[0] = 1;
    int s,t;
    rep(i,n){
        // show(nw^a[i]);
        int res = bt.query(nw^a[i]);
        // show(res);
        if(ans < res){
            ans = res;
            s = mp[res^(nw^a[i])];
            t = i+1;
            // cout << s << " " << t << "\n";
        }
        nw ^= a[i];
        if(mp.find(nw) == mp.end()){
            bt.add(nw);
            mp[nw] = i+2;
        }
    }
    cout << ans << " " << s << " " << t << "\n";
    return 0;
}

Submission Info

Submission Time
Task F - Maximum Segment XOR
User kopricky
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3295 Byte
Status WA
Exec Time 121 ms
Memory 19328 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 21
WA × 10
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 2, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3, 30, 31, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 1 ms 256 KB
10 AC 2 ms 640 KB
11 AC 2 ms 512 KB
12 AC 2 ms 384 KB
13 AC 7 ms 2176 KB
14 WA 9 ms 2432 KB
15 AC 10 ms 2816 KB
16 WA 54 ms 8960 KB
17 WA 34 ms 7808 KB
18 WA 121 ms 19328 KB
19 WA 1 ms 256 KB
2 AC 1 ms 256 KB
20 AC 1 ms 256 KB
21 AC 1 ms 256 KB
22 WA 1 ms 256 KB
23 AC 1 ms 256 KB
24 AC 1 ms 256 KB
25 AC 4 ms 768 KB
26 WA 2 ms 512 KB
27 WA 6 ms 1152 KB
28 AC 74 ms 12160 KB
29 WA 84 ms 13184 KB
3 AC 1 ms 256 KB
30 AC 48 ms 8832 KB
31 WA 110 ms 14720 KB
4 AC 1 ms 256 KB
5 AC 1 ms 256 KB
6 AC 1 ms 256 KB
7 AC 1 ms 256 KB
8 AC 1 ms 256 KB
9 AC 2 ms 512 KB