Submission #1318868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318868		kero	XOR (IZhO12_xor)	C++20	0 / 100	333 ms	44916 KiB

xor

#include <iostream>
#include<bits/stdc++.h>

#define KIRA ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F(i, a, b) for(int i=(a);i<(b);i++)
#define dF(i, a, b) for(int i=(a);i>=(b);i--)
#define ms(a, b) memset(a,b,sizeof(a))
#define si(a) ((int)a.size())
#define pi pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ul unsigned ll
#define ll long long
#define ld long double
#define all(v) (v).begin(), (v).end()
#define rall(v) v.rbegin(),v.rend()
#define sz(n) int(n.size())
#define endl '\n'
#define yes cout<<"YES\n";
#define no cout<<"NO\n";

#define cin(vec)        \
        for (auto &i : vec) \
        cin >> i
#define cout(vec)              \
        for (auto &i : vec)        \
        {                          \
            cout << i << char(32); \
        }                          \
        cout << endl;
using namespace std;

void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

struct TrieNode {
    int cnt;
    TrieNode *child[2]; // for bits
    //TrieNode *child[26]; // for strings
    int mnindx;
    TrieNode() {
        cnt = 0;
        mnindx = INT_MAX;
        ms(child, 0);
    }
};

class Trie {
private:
    TrieNode *root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert_str(const string s, int cnt) {
        TrieNode *cur = root;
        for (char c:s) {
            int i = c - '0';
            if (!cur->child[i])
                cur->child[i] = new TrieNode();
            cur = cur->child[i];
            //update
            cur->cnt += cnt;
        }
    }
    void insert_bits(const ll x,int cnt,int idx){
        TrieNode* cur = root;
        for(ll j = 30;j >= 0;j--){
            ll i = (x >> j) & 1;
            if (!cur->child[i])
                cur->child[i] = new TrieNode();
            cur = cur->child[i];
            //update
            cur->cnt += cnt;
            cur->mnindx = min(idx,cur->mnindx);
        }
    }

    ll mx_xor(ll x){
        TrieNode* cur = root;
        ll ans = 0;
        for(ll j = 30;j >= 0;j--){
            ll i = (x >> j) & 1;
            if (cur->child[1 - i] && cur->child[1 - i]->cnt > 0){
                ans|=(1ll<<j);
                cur = cur->child[1 - i];
            }else{
                cur = cur->child[i];
            }
        }
        return ans;
    }
    ll mn_xor(ll x){
        TrieNode* cur = root;
        ll ans = 0;
        for(ll j = 30;j >= 0;j--){
            ll i = (x >> j) & 1;
            if (cur->child[i]){
                cur = cur->child[i];
            }else{
                ans|=(1ll<<j);
                cur = cur->child[1 - i];
            }
        }
        return ans;
    }
    ll countXorGreaterThanK(int x,int k){
        TrieNode* cur = root;
        int ans = INT_MAX;
        for (int b = 30; b >= 0; --b) {
            if (!cur)break;
            int bx = (x >> b) & 1;
            int bk = (k >> b) & 1;

            if (bk == 1){
                cur = cur->child[1 - bx];
            }else{
                if (cur->child[1 - bx]) {
                    ans= min(ans,cur->child[1 - bx]->mnindx);
                }
                cur = cur->child[bx];
            }
        }
        return ans;
    }
    ll countXorLessThanK(int x,int k){
        TrieNode* cur = root;
        ll ans = 0;
        for (int b = 30; b >= 0; --b) {
            if (!cur)break;
            int bx = (x >> b) & 1;
            int bk = (k >> b) & 1;

            if (bk == 1){
                if (cur->child[bx])
                    ans+=cur->child[bx]->cnt;
                cur = cur->child[1 - bx];
            }else{
                cur = cur->child[bx];
            }
        }
        return ans;
    }


};

void solve() {
    int n,k;cin>>n>>k;
    vector<int>v(n);
    cin(v);
    vector<int>pre(n + 2);
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] ^ v[i - 1];
    }
    Trie trie;
    trie.insert_bits(0,1,0);
    int bestl = 1,mx = 0;
    for (int r = 1; r <= n; ++r) {
        int l = trie.countXorGreaterThanK(pre[r],k - 1);
        if (l != INT_MAX){
            int len = r - l;
            if (len > mx){
                mx = len;
                bestl = l + 1;
            }
        }
        trie.insert_bits(pre[r],1,r);
    }
    cout << bestl << ' ' << mx << '\n';
}

/*
 * Think twice, code once
 * Think of different approaches to tackle a problem: write them down.
 * Think of different views of the problem. don't look from only one side.
 * don't get stuck in one approach.
 * common mistakes: over_flow
 *                  - out_of_bound index
 *                  -infinite loop
 *                  -corner cases
 *                  -duplication counting.
 */
int main() {
    KIRA
    File();
    int t = 1;
    //cin >> t;
    int cases = 1;
    while (t--) {
        //cout << "Case " << cases++ << ": ";
        solve();
        //cout << "\n";

    }

    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void File()':
xor.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100