Submission #6021360


Source Code Expand

Copy
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <typeinfo>
#include <numeric>
#include <cassert>
#include <unistd.h>
#include <string.h>

using namespace std;

///////////////////////////////////////////////////////////////////////////////

#define pb push_back
#define V vector
#define M unordered_map
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll, ll> t2;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

struct UnionFind
{
        ull *parent, *count, *rank;

        UnionFind(ull n) {
                parent = new ull[n+1];
                count = new ull[n+1];
                rank = new ull[n+1];
                for (ull i = 0ULL; i < n+1; ++i) {
                        parent[i] = i;
                        count[i] = 1;
                        rank[i] = 0;
                }
        }

        ull root(ull i) {
                if (parent[i] == i) return i;
                parent[i] = root(parent[i]);
                return parent[i];
        }

        void unite(ull i, ull j) {
                ull rooti = root(i);
                ull rootj = root(j);

                if (rooti == rootj) return;

                if (rank[rootj] < rank[rooti]) {
                        parent[i] = parent[j] = parent[rootj] = rooti;
                        count[rooti] += count[rootj];
                }
                else {
                        parent[i] = parent[j] = parent[rooti] = rootj;
                        count[rootj] += count[rooti];
                        if (rank[rootj] == rank[rooti]) rank[rootj]++;
                }
        }

        bool same(ull i, ull j) {
                return root(i) == root(j);
        }
};

struct BIT
{
        ll *tree;
        ll size;

        BIT(ll n, ll init) {
                tree = new ll[n+1];
                size = n;
                rep (i, n+1) tree[i] = init;
        }

        // idx is 1 origin
        void add(ll idx, ll x) {
                assert(idx > 0LL);
                while (idx <= size) {
                        tree[idx] += x;
                        idx += (idx & (-idx));
                }
        }

        // idx is 1 origin
        ll sum(ll idx) {
                assert(idx > 0LL);
                ll ret = 0LL;
                while (idx > 0LL) {
                        ret += tree[idx];
                        idx -= (idx & (-idx));
                }
                return ret;
        }
};

void llin(ll &a)
{
        cin >> a;
}

void llinl1(auto &v, ll count)
{
        for (ll i = 0LL; i < count ; ++i) {
                ll a;
                cin >> a;
                v.push_back(a);
        }
}

void llinl2(auto &v, ll count)
{
        for (ll i = 0LL; i < count ; ++i) {
                ll a, b;
                cin >> a >> b;
                v.push_back(tuple<ll, ll>(a, b));
        }
}

void llinl3(auto &v, ll count)
{
        for (ll i = 0LL; i < count ; ++i) {
                ll a, b, c;
                cin >> a >> b >> c;
                v.push_back(tuple<ll, ll, ll>(a, b, c));
        }
}

void llina(auto &v, ll count)
{
        llinl1(v, count);
}

template <typename T>
T min(const V<T> v)
{
        T ret = v[0];
        for (auto i : v) ret = min(ret, i);
        return ret;
}

template <typename T>
T max(const V<T> v)
{
        T ret = v[0];
        for (auto i : v) ret = max(ret, i);
        return ret;
}

ll absll(ll x)
{
        if (x < 0) return -x;
        return x;
}

ll mod_mlt(ll x, ll y, ll mod)
{
        ll ret = 0LL;
        x %= mod;

        while (y) {
                if (y & 1LL) {
                        ret += x;
                        ret %= mod;
                }
                y >>= 1;
                x <<= 1;
                x %= mod;
        }

        return ret;
}

ll mod_pow(ll base, ll exp, ll mod)
{
        ll ret = 1LL;

        for ( ; exp; ) {
                if (exp & 1LL) {
                        ret *= base;
                        ret %= mod;
                }
                base = (base * base) % mod;
                exp >>= 1;
        }

        return ret;
}

ll mod_inv(ll x, ll mod)
{
        // available only when mod is prime
        return mod_pow(x, mod - 2LL, mod);
}

ll gcm(ll x, ll y)
{
        while (y != 0) {
                ll z = x % y;
                x = y;
                y = z;
        }
        return x;
}

template <typename T>
void sort(V<T> &v)
{
        sort(v.begin(), v.end());
}

template <typename T>
void sort_reverse(V<T> &v)
{
        sort(v.begin(), v.end(), greater<T>());
}

void get_divisors(V<ll> &retlist, ll x)
{
        for (ll i = 1LL; i < sqrt(x) + 3LL; ++i) {
                if (x % i == 0LL) {
                        retlist.push_back(i);
                        retlist.push_back(x / i);
                }
        }
}

void get_factors(V<ll> &retlist, ll x)
{
        for (ll i = 2LL; i < (ll)(sqrt(x)) + 3LL; ++i) {
                while (x % i == 0LL) {
                        retlist.pb(i);
                        x /= i;
                }
        }
        retlist.pb(x);
}

template <typename T>
void intersection(const set<T> &a, const set<T> &b,
                  set<T> &result)
{
        V<T> resultlist;

        set_intersection(a.begin(), a.end(),
                         b.begin(), b.end(),
                         back_inserter(resultlist));

        set<T> resultset(resultlist.begin(), resultlist.end());
        result = resultset;
}

ull combination(ll x, ll y)
{
        if (y > x / 2LL) y = x - y;

        ull ret = 1LL;
        for (ll i = 0LL; i < y; ++i) {
                ret *= x--;
                ret /= (i + 1LL);
        }

        return ret;
}

ull mod_combination(ll x, ll y, ll mod)
{
        if (y > x / 2LL) y = x - y;

        ll ret = 1;

        for (ll i = 0LL; i < y; ++i) {
                ret = (ret * x--) % mod;
                ret = (ret * mod_inv(i + 1LL, mod)) % mod;
        }

        return ret;
}

void make_linklist(const V<tuple<ll, ll>> &srclist, V<V<ll>> &dstlist)
{
        for (auto src : srclist) {
                ll a = get<0>(src);
                ll b = get<1>(src);
                dstlist[a].pb(b);
                dstlist[b].pb(a);
        }
}

void debug_print(auto xlist)
{
        for (auto x : xlist) cout << "-- " << x << endl;
}

int _main();
int main()
{
        cout << setprecision(12);
        return _main();
}

///////////////////////////////////////////////////////////////////////////////

struct Node {
        Node *child[2];
        int nlevel;

        Node(int lv) {
                child[0] = child[1] = NULL;
                nlevel = lv;
        }
};

int _main()
{
        ll n, level;
        llin(n); llin(level);

        V<string> slist;
        rep (i, n) {
                string s;
                cin >> s;
                slist.pb(s);
        }

        Node *root = new Node(0);
        Node *nodes[100050];
        int nodes_count = 0;
        nodes[nodes_count++] = root;

        for (auto s : slist) {
                Node *now = root;
                rep (i, s.size()) {
                        char idx = s[i] - '0';
                        if (now->child[idx] == NULL) {
                                now->child[idx] = new Node(i + 1);
                                nodes[nodes_count++] = now->child[idx];
                        }
                        now = now->child[idx];
                }
        }

        ll ans = 0LL;

        rep (i, nodes_count) {
                if (nodes[i]->child[0] && !(nodes[i]->child[1])) {
                        ll grundy = level - nodes[i]->nlevel;
                        grundy = grundy & -grundy;
                        ans = ans ^ grundy;
                }
                if (!(nodes[i]->child[0]) && nodes[i]->child[1]) {
                        ll grundy = level - nodes[i]->nlevel;
                        grundy = grundy & -grundy;
                        ans = ans ^ grundy;
                }
        }

        if (ans) cout << "Alice";
        else cout << "Bob";

        return 0;
}

///////////////////////////////////////////////////////////////////////////////

Submission Info

Submission Time
Task E - Prefix-free Game
User mjtai
Language C++14 (GCC 5.4.1)
Score 700
Code Size 8811 Byte
Status
Exec Time 9 ms
Memory 4352 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt
All 700 / 700 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt
Case Name Status Exec Time Memory
0_00.txt 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
0_03.txt 1 ms 256 KB
0_04.txt 1 ms 256 KB
0_05.txt 1 ms 256 KB
1_00.txt 1 ms 256 KB
1_01.txt 1 ms 256 KB
1_02.txt 1 ms 256 KB
1_03.txt 1 ms 256 KB
1_04.txt 1 ms 256 KB
1_05.txt 1 ms 256 KB
1_06.txt 9 ms 4352 KB
1_07.txt 9 ms 4352 KB
1_08.txt 7 ms 2304 KB
1_09.txt 9 ms 4352 KB
1_10.txt 9 ms 4352 KB
1_11.txt 5 ms 896 KB
1_12.txt 5 ms 384 KB
1_13.txt 5 ms 512 KB
1_14.txt 9 ms 1408 KB
1_15.txt 8 ms 1408 KB
1_16.txt 9 ms 1408 KB
1_17.txt 8 ms 1408 KB
1_18.txt 9 ms 1408 KB
1_19.txt 8 ms 1408 KB
1_20.txt 8 ms 1408 KB
1_21.txt 8 ms 1408 KB
1_22.txt 9 ms 1408 KB
1_23.txt 9 ms 1408 KB
1_24.txt 9 ms 1408 KB
1_25.txt 9 ms 1408 KB
1_26.txt 9 ms 1408 KB
1_27.txt 8 ms 1408 KB
1_28.txt 9 ms 1408 KB
1_29.txt 9 ms 1408 KB
1_30.txt 8 ms 1408 KB
1_31.txt 9 ms 1408 KB
1_32.txt 8 ms 1408 KB
1_33.txt 9 ms 1408 KB
1_34.txt 8 ms 1408 KB
1_35.txt 9 ms 1408 KB
1_36.txt 9 ms 1408 KB
1_37.txt 8 ms 1408 KB
1_38.txt 9 ms 1408 KB
1_39.txt 8 ms 1408 KB
1_40.txt 9 ms 1408 KB
1_41.txt 8 ms 1408 KB
1_42.txt 9 ms 1408 KB
1_43.txt 9 ms 1408 KB
1_44.txt 9 ms 1408 KB
1_45.txt 9 ms 1408 KB
1_46.txt 9 ms 1408 KB
1_47.txt 8 ms 1408 KB
1_48.txt 9 ms 1408 KB
1_49.txt 9 ms 1408 KB
1_50.txt 8 ms 1408 KB
1_51.txt 9 ms 1408 KB
1_52.txt 8 ms 1408 KB
1_53.txt 9 ms 1408 KB