1849F - XOR Partition - CodeForces Solution

// g++ ".cpp" -o ""; cat "-in.txt" | & "..exe"
// g++ .cpp -std=c++17 -o  && time ./ < -in.txt
// g++-12 .cpp -O2 -std=c++17 -o  && time ./ < -in.txt
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <cmath>
#include <ios>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <tuple>
#include <type_traits>
#include <chrono> 
#include <random>
#include <bitset>
#include <set>
#include <limits.h>
#include <list>
#include <stack>
#include <unordered_map>
#include <typeinfo>
#include <string.h>
#include <cstdint>
#include <numeric>
#include <cassert>
#include <sstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <boost/lexical_cast.hpp>
// using boost::lexical_cast;
using namespace std;
using namespace __gnu_pbds;
// Policy based data structures
/*
    S.find_by_order(k) => returns iterator to the kth largest element
                        S.find_by_order(sz) returns end(S)
    S.order_of_key(x) => number of items in the set that are strictly smaller than x
*/
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define endl "\n"
#define Re register
#define fori(i, s, n) for (Re int i = s; i < n; i++)
#define forii(i, s, n) for (Re int i = s; i > n; --i)
#define PB push_back
#define F first
#define S second
#define INF 0x3f3f3f3f
#define MINF 0x3f3f3f3f3f3f3f3fll
#define contain count
#define EB emplace_back
#define ld long double
#define ll long long
#define all(x) x.begin(), x.end()
#define foreach(x,in,s) for(const auto &x: s)
#define YES cout << "YES\n"
#define Yes cout << "Yes\n"
#define NO cout << "NO\n"
#define No cout << "No\n"
#define dbgx(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define sp(x) fixed << setprecision(x) 
#define pi acos(-1.0)
#define some(a,l,r) a.begin()+l,a.begin()+(r+1)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rng_seed(x) mt19937 rng(x)
#define uid(from,to) uniform_int_distribution<int>(from,to)
#define set(x, val) memset(x, val, sizeof(x))
#define urd(from,to) uniform_real_distribution<double>(from,to) int randint(int from=0,int to=1000000000){return uid(from,to)(rng);};
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define parity(n) __builtin_parityll(n)
#define lowerpos(a, x) (int)distance((a).begin(), lower_bound(all(a), x))
#define upperpos(a, x) (int)distance((a).begin(), upper_bound(all(a), x))
#define cube(n) cbrtl(n)
#define lg(n) __lg(n) + 1;
#define fast_io                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    template<typename L, typename R>
    size_t operator()(pair<L,R> const& Y) const{
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(Y.first * 31ull + Y.second + FIXED_RANDOM);
    }
};

template <typename K, typename V>
using hash_table = gp_hash_table<K, V, custom_hash>;
// inline ll lread(){register ll x=0,f=1;register char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;}
// inline int read(){register int x=0,f=1;register char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;}

const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // for grid problems
const int MOD = 1e9 + 7;
const int MODD = 998244353;
const long double PI = 3.14159265358979323851280895940618620443274267017841L;
const long double E = 2.718281828459045235428168107993940338928950950503355L;
const double EPS = 1e-9;
template<typename Head, typename ...Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}
int low_set_bit(int x){return x&(-x);}
template <typename T> 
void sort_unique(vector<T>& v){ 
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin(), 0);        
    //v.erase(unique(v.begin(), v.end()), v.end()); 
}
bool check(int mask,int pos){return mask&(1<<pos);}
int ser(int mask,int pos){return mask|(1<<pos);}
int flip(int mask,int pos){return mask^(1<<pos);}
int reset(int mask,int pos){return mask&~(1 << pos);}
template<class T>
void self_max(T &a, T b) { if(a < b) a = b; }
template<class T>
void self_min(T &a, T b) { if(a > b) a = b; }
template<class T>
void self_add(T &a, T b) { a += b; if(a > MOD) a -= MOD; }
template<class T>
void self_sub(T &a, T b) { a -= b; if(a < 0) a += MOD; }
vector<string> split(const string &s, char delim) {
    vector<string> e; stringstream ss(s);string item;
    while(getline(ss, item, delim)) e.push_back(item);
    return e;
}
//   gcd(x,y)=gcd(x-y,y);
//   gcd(a,b,c.....,z)=gcd(a,b-a,c-a,......z-a);
//   gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
//   lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).
//   if p%x==0 && q%x==0 then (p%q)%x==0
template<typename T> 
T gcd(T a, T b) { if(b == 0) return a; return gcd(b, a%b); }
template<class T, class ...V>
void self_max(T &a, T b, V... c) { if(a < b) a = b; self_max(a, c...); }
template<class T, class ...V>
void self_min(T &a, T b, V... c) { if(a > b) a = b; self_min(a, c...); }
template<class T, class ...V>
void self_add(T &a, T b, V... c) { a += b; if(a > MOD) a -= MOD; self_add(a, c...); }
template<class T, class ...V>
void self_sub(T &a, T b, V... c) { a -= b; if(a < 0) a += MOD; self_sub(a, c...); }
// https://www.math.utah.edu/~schwede/MichiganClasses/math185/NotationAndTerminology.pdf
// (x0,y0) -> (x,y)
// x = x0 + b/gcd(a,b) * k      (∀ k∈Z)
// y = y0 - a/gcd(a,b) * k
// ax + by = d        where d = gcd(a,b)
// 33x + 17y = d
// you are denormalize the equation until you can't get b = 0.
// once you get b = 0. Then you will get x = 1, y = 1.
// 33(1) = 17(1) + 16
// 17(1) = 16(1) + 1
// 16(1) = 1(16) + 0
// 1(1) = 0(0) + 1
// generalize it as ax = b(-y) + d.
// Stop when we reach at b = 0 here x a will be our gcd. Then recursively calculate newx and newy from bottom to up to reach at our original equation.
// newx = oldy and newy = oldx - (b/a)*oldy;
inline ll extgcd(ll a, ll &x, ll b, ll &y){ if (b == 0) { x = 1, y = 0; return a; } ll gcd = extgcd(b, y, a % b, x); y -= a / b * x; return gcd;}
template<typename T = int>
inline int bin_pow(T n, T exp, T MOD = 1e9 + 7) { n %= MOD; ll res = 1; while(exp) { if(exp & 1) { res = (res * n) % MOD; } n = (n * n) % MOD; exp >>= 1;} return (res) % MOD;}
template<typename T>
inline double bin_powd(double n, T exp, double MOD = 1e9 + 7) { fmod(n, MOD); double res = 1.00; while(exp) { if(exp & 1) { res = fmod(res * n, MOD); } n = fmod(n * n, MOD); exp >>= 1;} return fmod(res, MOD);}
ll moduloMultiplication(ll a,ll b,ll mod){ll res = 0;a %= mod;while (b){if (b & 1)res = (res + a) % mod;b >>= 1;}return res;}
template<typename T>
inline ll modInverse(T a, T modd = 1e9+ 7) { ll x, y; ll g = extgcd(a,x,modd,y); /* ll res = (x % modd + modd) % modd; return res; */ return x;}

// https://cp-algorithms.com/algebra/linear-diophantine-equation.html#the-degenerate-case
//     ax + by = c.  (diaphantie equation)
// =>     ax = c (mod b)
// =>     by = c (mod a)
// =>     (a/d)x = (c/d) (mod b/d),  where d = gcd(a,b)
// =>     x = (c/d) inv(a/d) (mod b/d)
// =>    if c == d, then x = inv(a/d) mod(b/d). we can actually get inverse using modInverse1.
template<typename T>
inline ll modInverse1(T a, T modd = 1e9 + 7) { return bin_pow(a, modd-2, modd); }
template<typename T>
unordered_map<int,int> factorize(int x) { unordered_map<int,int> ans; int j = 2; while(x > 1) { if(x % j == 0) { int cnt = 0; while(x % j == 0) { cnt++; x /= j; } ans[j] = cnt; } j++;} return ans; }

// https://en.wikipedia.org/wiki/Chinese_remainder_theorem
// https://brilliant.org/wiki/chinese-remainder-theorem/
// a = a1(mod m1)
// a = a2(mod m2)
// solve m1x + m2y = gcd(m1,m2) using extgcd.
// a  =  ∑ ai* Mi * Ni           where Ni = product of all [m1,m2,...,mi-1,mi+1,..,mk] except mi. and Mi is the inverse of Ni.
//    k=1->n
ll chinese(ll a, ll m, ll b, ll n) { ll x, y; extgcd(a,x,b,y); a = a*n*(y + m) % m + b*m*(x + n) % m; if(a >= m*n) a -= m*n; return a;}
ll chinese_common(ll a, ll m, ll b, ll n) { ll d = gcd(m,n); if((b -= a % n) < 0) b += n; if(b % d) return -1; return d * chinese((ll)0, m / d, b / d, n / d) + a;}
constexpr int Z = 1e5 + 5;

void init_code(){
    fast_io;
    #ifdef LOCAL
        freopen("Input.txt", "r", stdin);
        freopen("Output.txt", "w", stdout);
        freopen("Error.txt", "w", stderr);
    #endif
}

#ifdef LOCAL
 
    #define deb(args...)       cerr << "[ " #args << " ] : " , debug(args);
    #define debx(args...)      (Debugger(" ")),args
    #define debug(args...)     (Debugger()) , args
 
    class Debugger
    {
        public:
        Debugger(const std::string& _separator = ", ") :
        first(true), separator(_separator){}
 
        template<typename ObjectType>
        Debugger& operator , (const ObjectType& v)
        {
            if(!first)
                std::cerr << separator;
            std::cerr << v;
            first = false;
            return *this;
        }
        ~Debugger() {  std::cerr << endl;}
 
        private:
        bool first;
        std::string separator;
    };
 
    template <typename T1, typename T2>
    inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p)
    {
        return os << "(" << p.first << ", " << p.second << ")";
    }
 
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::vector<T>& v)
    {
        bool first = true;
        os << "[";
        for(unsigned int i = 0; i < v.size(); i++)
        {
            if(!first)
                os << ", ";
            os << v[i];
            first = false;
        }
        return os << "]";
    }
 
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::set<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
 
    template<typename T>
    inline std::ostream &operator << (std::ostream & os,const std::multiset<T>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii;
            first = false;
        }
        return os << "]";
    }
 
    template<typename T1, typename T2>
    inline std::ostream &operator << (std::ostream & os,const std::map<T1, T2>& v)
    {
        bool first = true;
        os << "[";
        for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii)
        {
            if(!first)
                os << ", ";
            os << *ii ;
            first = false;
        }
        return os << "]";
    }
 
#else
 
    #define deb(args...)
    #define debx(args...)
    #define debug(args...)
 
#endif


void pre(){

}

const int MXN = 3000021;
int A[MXN], B[MXN], cnt[MXN], pref[MXN], suf[MXN];
int n, m, q, k, total, ans, l, r, b, c, d, x, y, best, last, low, high;
ll sum;
vector<pair<int,int>> C;
priority_queue<int, vector<int>, greater<int>> pq;
string s, t;
vector<pair<int,int>> vp;
set<pair<int,int>> sp;
set<string> ss;
unordered_map<string, int> mps;
unordered_map<int,int> mpi;
pair<int, int> a[MXN];
char color[MXN];

// void process(int l, int r) {
//     if(l == r) {
//         // do something
//         return;
//     }
//     int mid = l + (r - l) >> 1;
//     process(l, mid);
//     process(mid + 1, r);
// }

// void solve(){
//     cin >> n;

//     fori(i, 0, n) {
//         cin >> A[i];
//     }

//     process(0, n - 1);
// }

void solve(){
    cin >> n;
    for(Re int i = 1; i <= n; i ++ ){
        cin >> a[i].first;
        a[i].second = i, color[i] = '0';
    }
 
    sort(a + 1, a + n + 1);
    
    function<int(int, int, int)> dfs = [&](int l, int r, int d) -> int {
        if(l > r) return (1 << 30);
        if(d < 0) return 0;
 
        Re int mid = l - 1;
        while(mid + 1 <= r && !(a[mid + 1].first >> d & 1)) mid ++ ;
        if(mid - l + 1 >= 5 || r - mid >= 5)
            return min(dfs(l, mid, d - 1), dfs(mid + 1, r, d - 1));
 
        Re int cnt = r - l + 1;
        Re int ans = -1, state = 0;
        for(Re int i = 0; i < (1 << cnt); i ++ )
        {
            int res = (1 << 30);
            for(Re int j = 0; j < cnt; j ++ )
            {
                int b1 = (i >> j & 1);
                for(Re int k = j + 1; k < cnt; k ++ )
                {
                    int b2 = (i >> k & 1);
                    if(b1 == b2)
                        res = min(res, a[l + j].first ^ a[l + k].first);
                }
            }
 
            if(res > ans)
            {
                ans = res;
                state = i;
            }
        }
 
        for(Re int i = 0; i < cnt; i ++ )
            if(state >> i & 1) color[a[l + i].second] = '1';
        return ans;
    };
 
    dfs(1, n, 30);
    cout << color + 1 << '\n';
}

signed main()
{
    fast_io;
    init_code();
    pre();
    cout << fixed << setprecision(6);
    // auto begin = chrono::high_resolution_clock::now();
    ll T = 1;
    // cin >> T;
    while (T--)
    {
        // cout << "Case #" << T << ": ";
        solve();
        // cout << endl;
        // auto end = chrono::high_resolution_clock::now();
        // auto duration = chrono::duration_cast<chrono::milliseconds> (end - begin).count();
        // cout << duration << " ms elapsed" << endl;
    }
    return 0;
}