提出 #23368014

---

ソースコード 拡げる

#include <bits/stdc++.h>
//#include <atcoder/all>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
//const ll mod = 1000000007;
template< typename T, int MAX_LOG >
struct BinaryTrie {
  BinaryTrie *nxt[2];
  T lazy;
  int exist;
  bool fill;
  vector< int > accept;

  BinaryTrie() : exist(0), lazy(0), nxt{nullptr, nullptr} {}

  void add(const T &bit, int bit_index, int id) {
    propagate(bit_index);
    if(bit_index == -1) {
      ++exist;
      accept.push_back(id);
    } else {
      auto &to = nxt[(bit >> bit_index) & 1];
      if(!to) to = new BinaryTrie();
      to->add(bit, bit_index - 1, id);
      ++exist;
    }
  }

  void add(const T &bit, int id) {
    add(bit, MAX_LOG, id);
  }

  void add(const T &bit) {
    add(bit, exist);
  }

  void del(const T &bit, int bit_index) {
    propagate(bit_index);
    if(bit_index == -1) {
      exist--;
    } else {
      nxt[(bit >> bit_index) & 1]->del(bit, bit_index - 1);
      exist--;
    }
  }

  void del(const T &bit) {
    del(bit, MAX_LOG);
  }


  pair< T, BinaryTrie * > max_element(int bit_index) {
    propagate(bit_index);
    if(bit_index == -1) return {0, this};
    if(nxt[1] && nxt[1]->size()) {
      auto ret = nxt[1]->max_element(bit_index - 1);
      ret.first |= T(1) << bit_index;
      return ret;
    } else {
      return nxt[0]->max_element(bit_index - 1);
    }
  }

  pair< T, BinaryTrie * > min_element(int bit_index) {
    propagate(bit_index);
    if(bit_index == -1) return {0, this};
    if(nxt[0] && nxt[0]->size()) {
      return nxt[0]->min_element(bit_index - 1);
    } else {
      auto ret = nxt[1]->min_element(bit_index - 1);
      ret.first |= T(1) << bit_index;
      return ret;
    }
  }

  T mex_query(int bit_index) { // distinct-values
    propagate(bit_index);
    if(bit_index == -1 || !nxt[0]) return 0;
    if(nxt[0]->size() == (T(1) << bit_index)) {
      T ret = T(1) << bit_index;
      if(nxt[1]) ret |= nxt[1]->mex_query(bit_index - 1);
      return ret;
    } else {
      return nxt[0]->mex_query(bit_index - 1);
    }
  }

  int64_t count_less(const T &bit, int bit_index) {
    propagate(bit_index);
    if(bit_index == -1) return 0;
    int64_t ret = 0;
    if((bit >> bit_index) & 1) {
      if(nxt[0]) ret += nxt[0]->size();
      if(nxt[1]) ret += nxt[1]->count_less(bit, bit_index - 1);
    } else {
      if(nxt[0]) ret += nxt[0]->count_less(bit, bit_index - 1);
    }
    return ret;
  }

  pair< T, BinaryTrie * > get_kth(int64_t k, int bit_index) { // 1-indexed
    propagate(bit_index);
    if(bit_index == -1) return {0, this};
    if((nxt[0] ? nxt[0]->size() : 0) < k) {
      auto ret = nxt[1]->get_kth(k - (nxt[0] ? nxt[0]->size() : 0), bit_index - 1);
      ret.first |= T(1) << bit_index;
      return ret;
    } else {
      return nxt[0]->get_kth(k, bit_index - 1);
    }
  }

  pair< T, BinaryTrie * > max_element() {
    assert(exist);
    return max_element(MAX_LOG);
  }

  pair< T, BinaryTrie * > min_element() {
    assert(exist);
    return min_element(MAX_LOG);
  }

  T mex_query() {
    return mex_query(MAX_LOG);
  }

  int size() const {
    return exist;
  }

  void xorpush(const T &bit) {
    lazy ^= bit;
  }

  int64_t count_less(const T &bit) {
    return count_less(bit, MAX_LOG);
  }

  pair< T, BinaryTrie * > get_kth(int64_t k) {
    assert(0 < k && k <= size());
    return get_kth(k, MAX_LOG);
  }

  void propagate(int bit_index) {
    if((lazy >> bit_index) & 1) swap(nxt[0], nxt[1]);
    if(nxt[0]) nxt[0]->lazy ^= lazy;
    if(nxt[1]) nxt[1]->lazy ^= lazy;
    lazy = 0;
  }
};


ll f(vector<ll> v, ll b) {
    //cerr << v.size() << " " << b << endl;
    if(v.empty()) return 0;
    if(b == -1) return 0;
    vector<ll> a[2];
    for(int i = 0; i < v.size(); i++) {
        ll idx = (v[i] >> b) & 1;
        a[idx].push_back(v[i]);
    }
    if(a[0].size() % 2 == 0) {
        for(auto &val : a[1]) {
            val ^= (1 << b);
        }
        ll ret = max(f(a[0], b-1), f(a[1], b-1));
        return ret;
    } else {
        BinaryTrie<ll, 30> Trie;
        //cerr << b << " " << a[0].size() << " " << a[1].size() << endl;
        for(auto tmp : a[0]) Trie.add(tmp);
        ll ret = INF;
        for(auto tmp : a[1]) {
            Trie.xorpush(tmp);
            chmin(ret, Trie.min_element().first);
            Trie.xorpush(tmp);
        }
        return ret;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<ll> A(2 * N);
    for(int i = 0; i < 2 * N; i++) cin >> A[i];
    ll ans = f(A, 29);
    cout << ans << endl;
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘ll f(std::vector<long long int>, ll)’:
./Main.cpp:180:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  180 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~
./Main.cpp: In instantiation of ‘BinaryTrie<T, MAX_LOG>::BinaryTrie() [with T = long long int; int MAX_LOG = 30]’:
./Main.cpp:191:28:   required from here
./Main.cpp:32:7: warning: ‘BinaryTrie<long long int, 30>::exist’ will be initialized after [-Wreorder]
   32 |   int exist;
      |       ^~~~~
./Main.cpp:31:5: warning:   ‘long long int BinaryTrie<long long int, 30>::lazy’ [-Wreorder]
   31 |   T lazy;
      |     ^~~~
./Main.cpp:36:3: warning:   when initialized here [-Wreorder]
   36 |   BinaryTrie() : exist(0), lazy(0), nxt{nullptr, nullptr} {}
      |   ^~~~~~~~~~
./Main.cpp:31:5: warning: ‘BinaryTrie<long long int, 30>::lazy’ will be initialized after [-Wreorder]
   31 |   T lazy;
      |     ^~~~
./Main.cpp:30:15: warning:   ‘BinaryTrie<long long int, 30>* BinaryTrie<long long int, 30>::nxt [2]’ [-Wreorder]
   30 |   BinaryTrie *nxt[2];
      |               ^~~
./Main.cpp:36:3: warning:   when initialized here [-Wreorder]
   36 |   BinaryTrie() : exist(0), lazy(0), nxt{nullptr, nullptr} {}
      |   ^~~~~~~~~~

ジャッジ結果