Submission #321250

#	Time	Username	Problem	Language	Result	Execution time	Memory
321250		mat_v	XOR (IZhO12_xor)	C++14	100 / 100	241 ms	120676 KiB

xor

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,x;
int maks;
int niz[250005];
int dokle = 0;
struct node{
    int l[2];
    int br = 1e9;
    int najm = 1e9;
}tri[250005 * 30];


void dodaj(int broj, int idx){
    int r = 0;
    //tri[0].br = -1;
    fb(i,30,0){
        int tr = 0;
        if((1<<i)&broj)tr = 1;
        if(tri[r].l[tr] != 0){
            r = tri[r].l[tr];
        }
        else{
            tri[r].l[tr] = dokle + 1;
            dokle++;
            r = dokle;
            tri[r].najm = 1e9;
        }
    }
    tri[r].br = min(tri[r].br, idx);
}

int dfs(int broj){
    int tr = 1e9;
    if(tri[broj].l[0] != 0)tr = min(tr, dfs(tri[broj].l[0]));
    if(tri[broj].l[1] != 0)tr = min(tr, dfs(tri[broj].l[1]));
    tr = min(tr, tri[broj].br);
    tri[broj].najm = tr;
    return tr;
}

int kveri(int broj){
    int r = 0;
    int ans = 1e9;
    bool naso = 0;
    fb(i,30,0){
        int p1 = (((1<<i)&broj)>0);
        int p2 = (((1<<i)&x)>0);
        //cout << i << " " << r << " " << p1 << " " << p2 << " " << ans << "\n";
        if(p2 == 1){
            int sta = p1^p2;
            if(tri[r].l[sta] == 0){
                if(!naso)return 1e9;
            }
            //cout << r << " " << tri[r].l[sta];
            r = tri[r].l[sta];
            continue;
        }
        int sta = tri[r].l[1^p1];
        if(sta != 0){
            naso = 1;
            int dete = tri[r].l[sta];
           // if(tri[sta].najm == 0)cout << i << "\n";
            ans = min(ans, tri[sta].najm);
        }
        sta = p1;
        if(tri[r].l[sta] == 0){
            return ans;
        }
        r = tri[r].l[sta];
    }
    ans = min(ans, tri[r].najm);
    return ans;
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> x;
    int ks = 0;
    niz[0] = 0;
    dodaj(0,0);
    ff(i,0,n - 1){
        int t;
        cin >> t;
        ks ^= t;
        niz[i + 1] = ks;
        maks = max(maks, ks);
        dodaj(ks,i+1);
    }
    dfs(0);
    int sol = 0;
    //cout << kveri(1) << "\n";
    //return 0;
    int poz = 0;
    ff(i,0,n){
        int sta = kveri(niz[i]);
        sta++;
        if(sta > i)continue;
        int raz = (i - sta + 1);
        if(raz > sol){
            sol = raz;
            poz = sta;
        }
    }
    cout << poz << " " << sol << "\n";
    return 0;
}

Compilation message (stderr)

xor.cpp: In function 'void dodaj(int, int)':
xor.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
xor.cpp:37:5: note: in expansion of macro 'fb'
   37 |     fb(i,30,0){
      |     ^~
xor.cpp: In function 'int kveri(int)':
xor.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
xor.cpp:66:5: note: in expansion of macro 'fb'
   66 |     fb(i,30,0){
      |     ^~
xor.cpp:82:17: warning: unused variable 'dete' [-Wunused-variable]
   82 |             int dete = tri[r].l[sta];
      |                 ^~~~
xor.cpp: In function 'int main()':
xor.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
xor.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,0,n - 1){
      |     ^~
xor.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
xor.cpp:118:5: note: in expansion of macro 'ff'
  118 |     ff(i,0,n){
      |     ^~

• Subtask 1: 100 / 100