Submission #6015714


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<char MIN_CHAR, int SIGMA> struct trie {
    struct node {
        // link: contains trie links + failure links
        // suff: link to longest proper suffix that exists in the trie
        // dict: link to longest suffix that exists in the dictionary
        // wct: number of suffixes that are words in the dictionary
        // wid: index of this node's word in the dictionary
        array<int, SIGMA> link;
        int depth, suff, dict, wct, wid;
        node(int depth) : depth(depth), suff(0), dict(0), wct(0), wid(-1) {
            fill(all(link), 0);
        }
        int& operator [] (char c) { return link[c - MIN_CHAR]; }
    };

    int W;
    vector<node> nodes;

    /*
     * Builds a trie over the given word set and calculates Aho-Corasick links.
     * Runs in O(sum of word lengths).
     */
    trie() {}
    trie(auto begin, auto end) : W(0), nodes({ node(0) }) {
        int L = 0; for (auto it = begin; it != end; it++) L += it->size();
        nodes.reserve(L);

        for (auto it = begin; it != end; it++) {
            int loc = 0;
            for (char c : *it) {
                assert(MIN_CHAR <= c && c < MIN_CHAR + SIGMA);
                if (!nodes[loc][c]) {
                    nodes[loc][c] = nodes.size();
                    nodes.push_back(nodes[loc].depth + 1);
                }
                loc = nodes[loc][c];
            }
            nodes[loc].dict = loc;
            nodes[loc].wct = 1;
            nodes[loc].wid = W++;
        }

        /*for (queue<int> bfs({0}); !bfs.empty(); bfs.pop()) {
            int loc = bfs.front(), fail = nodes[loc].suff;
            if (!nodes[loc].dict)
                nodes[loc].dict = nodes[fail].dict;
            nodes[loc].wct += nodes[fail].wct;

            for (char c = MIN_CHAR; c < MIN_CHAR + SIGMA; c++) {
                int& succ = nodes[loc][c];
                if (succ) {
                    nodes[succ].suff = loc ? nodes[fail][c] : 0;
                    bfs.push(succ);
                } else succ = nodes[fail][c];
            }
        }*/
    }

    /*
     * Computes and returns the number of appearances of each word in the dictionary
     * as a substring of the given string.
     *
     * Runs in O(length of string to be searched + number of words in the dictionary).
     */
    vi matches(const string& text) const {
        vi res(W);
        priority_queue<pair<int, int>> found;

        int loc = 0;
        for (char c : text) {
            loc = nodes[loc].link[c - MIN_CHAR];
            int match = nodes[loc].dict;
            if (match) {
                if (!res[nodes[match].wid]++)
                    found.push({ nodes[match].depth, match });
            }
        }

        while (!found.empty()) {
            int loc = found.top().second; found.pop();
            int nxt = nodes[nodes[loc].suff].dict;
            if (nxt) {
                if (!res[nodes[nxt].wid]) found.push({ nodes[nxt].depth, nxt });
                res[nodes[nxt].id] += res[nodes[loc].id];
            }
        }
        return res;
    }

    /*
     * Computes and returns the total number of appearances of all words in the
     * dictionary as substrings of the given string.
     *
     * Runs in O(length of string to be searched).
     */
    ll search(const string& text) const {
        ll res = 0;
        int loc = 0;
        for (char c : text) {
            loc = nodes[loc].link[c - MIN_CHAR];
            res += nodes[loc].wct;
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    /*const int MAXB = 64;

    vi nim(MAXB + 1);

    for (int b = 0; b <= MAXB; b++) {
        vi seen(MAXB + 2);
        seen[0] = true;
        for (int l = 1, n = 0; l <= b; l++) {
            n ^= nim[b-l];
            seen[n] = true;
        }

        while (seen[nim[b]])
            nim[b]++;

        int tr = 0;
        while (b & (1 << tr)) tr++;
        assert( ((b+1)&(-b-1)) == nim[b] );
    }*/

    auto nimber = [](ll b) {
        return ((b + 1) & (-b - 1));
    };

    int N; ll L;
    cin >> N >> L;

    vector<string> s(N);
    for (string& str : s) cin >> str;
    trie<'0', 2> tr(all(s));

    ll res = 0;
    for (auto& n : tr.nodes) {
        int ch = (n['0'] != 0) + (n['1'] != 0);
        if (ch == 1) {
            res ^= nimber(L - n.depth - 1);
        }
    }
    cout << (res ? "Alice" : "Bob") << endl;

    return 0;
}

Submission Info

Submission Time
Task E - Prefix-free Game
User socketnaut
Language C++14 (GCC 5.4.1)
Score 700
Code Size 5219 Byte
Status
Exec Time 5 ms
Memory 6272 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 5 ms 6224 KB
1_07.txt 5 ms 6272 KB
1_08.txt 3 ms 2816 KB
1_09.txt 4 ms 3200 KB
1_10.txt 3 ms 3200 KB
1_11.txt 2 ms 768 KB
1_12.txt 2 ms 384 KB
1_13.txt 2 ms 384 KB
1_14.txt 3 ms 1152 KB
1_15.txt 3 ms 1152 KB
1_16.txt 3 ms 1152 KB
1_17.txt 4 ms 2688 KB
1_18.txt 4 ms 2816 KB
1_19.txt 3 ms 1152 KB
1_20.txt 4 ms 2944 KB
1_21.txt 3 ms 1152 KB
1_22.txt 4 ms 2944 KB
1_23.txt 3 ms 1152 KB
1_24.txt 3 ms 1152 KB
1_25.txt 3 ms 1152 KB
1_26.txt 4 ms 2944 KB
1_27.txt 4 ms 2688 KB
1_28.txt 4 ms 2816 KB
1_29.txt 3 ms 1152 KB
1_30.txt 3 ms 1152 KB
1_31.txt 3 ms 1152 KB
1_32.txt 3 ms 1152 KB
1_33.txt 4 ms 2944 KB
1_34.txt 3 ms 1152 KB
1_35.txt 3 ms 1152 KB
1_36.txt 3 ms 1152 KB
1_37.txt 3 ms 1152 KB
1_38.txt 4 ms 2816 KB
1_39.txt 3 ms 1152 KB
1_40.txt 4 ms 2944 KB
1_41.txt 3 ms 1152 KB
1_42.txt 3 ms 1152 KB
1_43.txt 3 ms 1152 KB
1_44.txt 4 ms 3072 KB
1_45.txt 4 ms 2944 KB
1_46.txt 3 ms 1152 KB
1_47.txt 3 ms 1152 KB
1_48.txt 3 ms 1152 KB
1_49.txt 3 ms 1152 KB
1_50.txt 3 ms 1152 KB
1_51.txt 3 ms 1152 KB
1_52.txt 4 ms 3072 KB
1_53.txt 4 ms 2944 KB