제출 #1364495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364495		vjudge1	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	344 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define ll long long
using l = int64_t;
#define int long long
void Fast() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}
const int N= 2e5 + 5;
const int mod = 998244353;
const ll INF = 1e15;
struct Trie {
    int mxbit = 30;
    struct Node {
        int adj[2]{};
        int &operator[](int x) {
            return adj[x];
        }
        int sz=0;
        int idx=-2;
    };
    vector<Node> trie;
    int newNode() {
        trie.emplace_back();
        return trie.size() - 1;
    }
    void init() {
        trie.clear();
        newNode();
    }
    int sz(int u) {
        return trie[u].sz;
    }
    Trie() { init();}
    void update(int n,int op,int idx) {
        int u = 0;
        for (int i = mxbit-1 ; i >= 0 ; i--) {
            int bit = (n>>i)&1;
            if (!trie[u][bit]){trie[u][bit]=newNode();}
            u = trie[u][bit];
            if (trie[u].idx==-2)trie[u].idx=idx;
            trie[u].sz+=op;
        }
        if (trie[u].idx==-2)trie[u].idx=idx;
    }
    int query(int x,int k) {
        int res=INF;
        int u = 0;
        for (int i = mxbit - 1; ~i; --i) {
            int chx = x>>i&1;
            int chk = k>>i&1;
            int o = trie[u][!chx];
            int z = trie[u][chx];
            if (!chk) {
                if (o) res = min(res, trie[o].idx);
                u=z;
            }
            else u = o;
            if (!u) break;
        }
        if (trie[u].idx>-2)res=min(res,trie[u].idx);
        if (res==INF) return -2;
        return res;
    }
};
void solve() {
    Trie trie;
    int n,k;cin>>n>>k;
    vector<ll>v(n);
    for (int i = 0 ; i < n ; i++)cin>>v[i];
    ll pr=0;
    ll mx=0;
    ll idx;
    trie.update(0, 1,-1);
    for (int i = 0 ; i < n ; i++) {
        pr ^= v[i];
        int tmp = trie.query(pr , k);
        if (tmp!=-2) {
            if (i-tmp>mx) {
                mx=i-tmp;
                idx=tmp+1;
            }
        }
        trie.update(pr, 1,i);
    }
    cout<<idx+1<<" " <<mx<<"\n";
}
int32_t main() {
    Fast();
    int tc = 1;
    //cin >> tc;
    for (int test = 1; test <= tc; ++test) {
        //cout << "Case " << test << ":\n";
        solve();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

• 서브태스크 1: 0 / 100