Submission #321250

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321250	2020-11-11T17:32:30 Z	mat_v	XOR (IZhO12_xor)	C++14	100 / 100	241 ms	120676 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	117732 KB	Output is correct
2	Correct	61 ms	117732 KB	Output is correct
3	Correct	68 ms	117732 KB	Output is correct
4	Correct	64 ms	117732 KB	Output is correct
5	Correct	70 ms	118008 KB	Output is correct
6	Correct	72 ms	117988 KB	Output is correct
7	Correct	71 ms	117988 KB	Output is correct
8	Correct	79 ms	118016 KB	Output is correct
9	Correct	121 ms	118884 KB	Output is correct
10	Correct	120 ms	118884 KB	Output is correct
11	Correct	120 ms	118884 KB	Output is correct
12	Correct	121 ms	118884 KB	Output is correct
13	Correct	120 ms	118884 KB	Output is correct
14	Correct	121 ms	118884 KB	Output is correct
15	Correct	123 ms	118884 KB	Output is correct
16	Correct	120 ms	118884 KB	Output is correct
17	Correct	233 ms	120676 KB	Output is correct
18	Correct	237 ms	120676 KB	Output is correct
19	Correct	241 ms	120676 KB	Output is correct
20	Correct	237 ms	120676 KB	Output is correct