Submission #1003039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003039		PurpleCrayon	Spy 3 (JOI24_spy3)	C++17	99 / 100	313 ms	143020 KiB

Aoi

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

namespace {

const ll INF = 1e18+10;
const int N = 2e4+10, Q = 16;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

vector<int> tree[N];
int mine[N];

int dfs_sub(int c) {
    int ans = 0;
    if (mine[c] != -1) ans |= 1 << mine[c];
    for (int nxt : tree[c]) ans |= dfs_sub(nxt);
    return ans;
}

string enc(ll x, int len) {
    string ans;
    for (int i = 0; i < len; i++) {
        ans += char('0' + x % 2);
        x /= 2;
    }
    return ans;
}

string build_tree(int mask, map<int, int>& peel) {
    if (__builtin_popcount(mask) == 1) return "";
    return build_tree(peel[mask], peel) + "0" + build_tree(mask ^ peel[mask], peel) + "1";
}

ll memo_tot[1 << Q];
ll fact[Q + 1];
ll nck(ll a, ll b) {
    return fact[a] / fact[b] / fact[a - b];
}

ll cnt_tot(int mask, map<int, int>& peel) {
    if (memo_tot[mask] != -1) return memo_tot[mask];
    if (__builtin_popcount(mask) == 1) return 1;

    assert(peel.count(mask));
    int part = peel[mask];
    return cnt_tot(part, peel) * cnt_tot(mask ^ part, peel) * nck(__builtin_popcount(mask) - 1, __builtin_popcount(part) - 1);
}

ll memo_less[1 << Q][Q][Q];
ll cnt_less(int l, int r, int mask, const vector<int>& p, map<int, int>& peel) { // number of things less than it
    assert(__builtin_popcount(mask) == r - l + 1);
    if (memo_less[mask][l][r] != -1) return memo_less[mask][l][r];
    if (l == r) {
        return __builtin_ctz(mask) < p[l];
    }

    int who_peel = 0;
    for (int i = l; i <= r; i++) who_peel |= 1 << p[i];
    // cerr << l << ' ' << r << ' ' << mask << ' ' << who_peel << endl;
    assert(peel.count(who_peel));
    // cerr << "peel: " << peel[who_peel] << endl;
    int k = __builtin_popcount(peel[who_peel]);
    ll ans = 0;
    for (int i = mask; ; i = (i - 1) & mask) {
        if (__builtin_popcount(i) == k && __builtin_ctz(mask) == __builtin_ctz(i)) {
            // cerr << "trans: " << i << endl;
            ans += cnt_less(l, l + k - 1, i, p, peel) * cnt_tot(who_peel ^ peel[who_peel], peel);
        }

        if (i == 0) break;
    }

    int rest = mask;
    for (int i = l; i < l + k; i++) {
        if ((rest >> p[i]) & 1 ^ 1) {
            rest = -1;
            break;
        }

        rest ^= 1 << p[i];
    }

    if (rest != -1 && __builtin_ctz(rest ^ mask) == __builtin_ctz(mask)) {
        ans += cnt_less(l + k, r, rest, p, peel);
    }

    return memo_less[mask][l][r] = ans;
}

vector<int> v;
void sets_rec(const string& s, int l, int r, int prv) {
    int me = 0;
    int cnt = (r - l + 1) / 2 + 1;
    for (int i = 0; i < cnt; i++)
        me |= 1 << (prv + i);
    v.push_back(me);

    if (l > r) {
        return;
    }

    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            sets_rec(s, l, i-1, prv);
            sets_rec(s, i+1, r-1, prv + (i-1 - l + 1) / 2 + 1);
            break;
        }
    }
}


vector<int> build_sets(string s, vector<int> p) { // given peel, return a list of relevant sets
    int q = sz(p);
    assert(sz(s) == 2 * (q - 1));
    v.clear();
    sets_rec(s, 0, sz(s)-1, 0);

    vector<int> ans{0};
    for (int x : v) {
        int y = 0;
        for (int i = 0; i < sz(p); i++) {
            if ((x >> i) & 1)
                y |= 1 << p[i];
        }

        ans.push_back(y);
    }

    return ans;
}

}

string aoi(int n, int m, int q, int k, vector<int> A, vector<int> B, vector<long long> C, vector<int> t, vector<int> x) {
    vector<vector<pair<int, ll>>> adj(n);
    map<pair<int, int>, int> mp;
    for (int i = 0; i < m; i++) {
        adj[A[i]].emplace_back(B[i], C[i]);
        adj[B[i]].emplace_back(A[i], C[i]);
        mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    }

    vector<int> par(n, -1);
    vector<ll> dist(n, INF);
    min_pq<pair<ll, int>> pq;
    pq.push({dist[0] = 0, 0});
    while (sz(pq)) {
        auto [d_c, c] = pq.top(); pq.pop();
        if (d_c != dist[c]) continue;
        for (auto [nxt, w] : adj[c]) {
            if (dist[nxt] > dist[c] + w) {
                par[nxt] = c;
                pq.push({dist[nxt] = dist[c] + w, nxt});
            }
        }
    }

    vector<int> par_ed(n, -1);
    for (int i = 1; i < n; i++) {
        par_ed[i] = mp[{i, par[i]}];
        tree[par[i]].push_back(i);
        // cerr << "par[" << i << "] = " << par[i] << ' ' << par_ed[i] << endl;
    }

    memset(mine, -1, sizeof(mine));
    for (int i = 0; i < q; i++) mine[t[i]] = i;

    vector<int> sub_mask(k);
    for (int i = 0; i < k; i++) {
        int a = A[x[i]], b = B[x[i]];
        if (par[b] != a) swap(a, b);
        if (par[b] != a) continue; // not in the tree
        sub_mask[i] = dfs_sub(b);
        // cerr << "sub_mask[" << i << "] = " << sub_mask[i] << endl;
    }

    for (int i = 0; i < k; i++) {
        for (int j = 0; j < i; j++) {
            int one = sub_mask[i], two = sub_mask[j];
            if (one < two) swap(one, two);
            assert((one & two) == 0 || (one & two) == two);
        }
    }

    vector<int> masks = sub_mask;
    sort(masks.begin(), masks.end(), [&](int x, int y) {
        return make_pair(__builtin_popcount(x), x) < make_pair(__builtin_popcount(y), y);
    });

    masks.resize(unique(masks.begin(), masks.end()) - masks.begin());


    vector<pair<int, vector<int>>> groups;
    for (int i = 0; i < q; i++) {
        groups.push_back({1 << i, {i}});
    }

    map<int, int> peel;
    for (int x : masks) {
        // cerr << "mask: " << x << endl;
        vector<vector<int>> use;
        auto new_groups = groups; new_groups.clear();
        sort(groups.begin(), groups.end(), [&](auto one, auto two) { return one.second < two.second; });

        int left = x;
        for (auto [y, v] : groups) {
            if ((y & x) == y) {
                use.push_back(v);

                // if (left != y) cerr << "add peel: " << left << ' ' << y << endl;
                if (left != y) peel[left] = y;
                left ^= y;
            } else {
                new_groups.push_back({y, v});
            }
        }

        assert(left == 0);
        vector<int> me;
        for (auto v : use) for (int y : v) me.push_back(y);
        new_groups.push_back({x, me});
        
        swap(groups, new_groups);
    }

    vector<int> p;
    int left = (1 << q) - 1;
    sort(groups.begin(), groups.end(), [&](auto one, auto two) { return one.second < two.second; });
    for (auto [y, v] : groups) {
        // if (left != y) cerr << "add peel: " << left << ' ' << y << endl;
        if (left != y) peel[left] = y;
        left ^= y;
        for (int x : v) p.push_back(x);
    }
    assert(left == 0);

    /*
    cerr << "p: ";
    for (int x : p) cerr << x << ' ';
    cerr << endl;
    */

    memset(memo_less, -1, sizeof(memo_less));
    memset(memo_tot, -1, sizeof(memo_tot));
    fact[0] = 1;
    for (int i = 1; i <= Q; i++)
        fact[i] = fact[i-1] * i;

    ll tot_cnt = cnt_tot((1 << q) - 1, peel);
    // cerr << "tot_cnt: " << tot_cnt << endl;
    ll perm_idx = cnt_less(0, q-1, (1 << q) - 1, p, peel);
    // cerr << "perm_idx: " << perm_idx << endl;

    const int BITS = 40;
    assert(perm_idx < tot_cnt);
    assert(tot_cnt < (1LL << BITS));
    string s_tree = build_tree((1 << q) - 1, peel);
    // cerr << s_tree << endl;
    string ans = enc(perm_idx, BITS) + s_tree;

    auto st = build_sets(s_tree, p);
    /*
    cerr << "st: "; for (int x : st) cerr << x << ' ';
    cerr << endl;
    */

    assert(sz(st) <= 32);
    for (int i = 0; i < k; i++) {
        int me = sub_mask[i];
        int use = -1;
        for (int j = 0; j < sz(st); j++) {
            if (st[j] == me) {
                use = j;
                break;
            }
        }

        assert(use != -1);
        ans += enc(use, 5);
    }

    return ans;
}

Bitaro

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

namespace {

const ll INF = 1e18+10;
const int N = 2e4+10, Q = 16;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

ll dec(string s) {
    reverse(s.begin(), s.end());

    ll ans = 0;
    for (char c : s) {
        ans *= 2;
        ans += c - '0';
    }
    return ans;
}

ll memo_ways[3 * Q][3 * Q];
ll fact[Q+1];

ll nck(int n, int k) { 
    assert(n >= k);
    return fact[n] / fact[k] / fact[n-k];
}


int need[Q];

void build_need(const string& s, int l, int r, int prv) {
    int me = 0;
    int cnt = (r - l + 1) / 2 + 1;
    if (l > r) {
        return;
    }

    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            int nxt_prv = prv + (i-1 - l + 1) / 2 + 1;
            need[prv] |= 1 << nxt_prv;
            // cerr << "need: " << prv << ' ' << nxt_prv << endl;
            build_need(s, l, i-1, prv);
            build_need(s, i+1, r-1, nxt_prv);
            break;
        }
    }
}

ll get_cnt(vector<int> p) {
    int q = sz(p);
    vector<int> loc(q, -1);
    for (int i = 0; i < q; i++) {
        if (p[i] != -1) {
            loc[p[i]] = i;
        }
    }

    vector<ll> pdp(1 << q); pdp[0] = 1;
    for (int rep = 0; rep < q; rep++) {
        vector<ll> ndp(1 << q);
        for (int mask = 0; mask < (1 << q); mask++) if (pdp[mask]) { 
            for (int j = 0; j < q; j++) if ((mask >> j) & 1 ^ 1) {
                if (loc[rep] != -1 && j != loc[rep]) continue;
                if (need[j] & mask) continue;
                ndp[mask | (1 << j)] += pdp[mask];
            }
        }
        swap(pdp, ndp);
    }

    return pdp[(1 << q) - 1];
}

vector<int> build_perm(ll perm_idx, string s_tree) {
    int q = sz(s_tree) / 2 + 1;
    build_need(s_tree, 0, sz(s_tree)-1, 0);

    vector<int> p(q, -1);
    vector<bool> used(q, 0);
    for (int i = 0; i < q; i++) {
        for (int j = 0; j < q; j++) if (!used[j]) {
            p[i] = j;
            ll cur = get_cnt(p);
            if (cur > perm_idx) {
                used[j] = 1;
                break;
            } else {
                perm_idx -= cur;
            }
        }
    }

    assert(perm_idx == 0);
    return p;
}

vector<int> v;
void sets_rec(const string& s, int l, int r, int prv) {
    int me = 0;
    int cnt = (r - l + 1) / 2 + 1;
    for (int i = 0; i < cnt; i++)
        me |= 1 << (prv + i);
    v.push_back(me);

    if (l > r) {
        return;
    }

    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            sets_rec(s, l, i-1, prv);
            sets_rec(s, i+1, r-1, prv + (i-1 - l + 1) / 2 + 1);
            break;
        }
    }
}


vector<int> build_sets(string s, vector<int> p) { // given peel, return a list of relevant sets
    int q = sz(p);
    assert(sz(s) == 2 * (q - 1));
    v.clear();
    sets_rec(s, 0, sz(s)-1, 0);

    vector<int> ans{0};
    for (int x : v) {
        int y = 0;
        for (int i = 0; i < sz(p); i++) {
            if ((x >> i) & 1)
                y |= 1 << p[i];
        }

        ans.push_back(y);
    }

    return ans;
}
}


void bitaro(int n, int m, int q, int k, vector<int> A, vector<int> B, vector<long long> C, vector<int> t, vector<int> x, string s) {
    fact[0] = 1;
    for (int i = 1; i <= Q; i++) {
        fact[i] = fact[i-1] * i;
    }

    const int BITS = 40;
    ll perm_idx = dec(s.substr(0, BITS));
    string s_tree = s.substr(BITS, 2 * (q - 1));
    string rest = s.substr(BITS + 2 * (q - 1));

    // cerr << s_tree << ' ' << perm_idx << endl;
    vector<int> p = build_perm(perm_idx, s_tree);
    /*
    cerr << "bitaro p: "; for (int x : p) cerr << x << ' ';
    cerr << endl;
    */
    auto st = build_sets(s_tree, p);
    /*
    cerr << "bitaro st: ";
    for (int x : st) cerr << x << ' ';
    cerr << endl;
    */

    vector<vector<int>> mine(q);
    for (int i = 0; i < k; i++) {
        int mask = st[dec(rest.substr(i * 5, 5))];
        // cerr << "sub_mask[" << i << "] = " << mask << endl;
        for (int j = 0; j < q; j++) {
            if ((mask >> j) & 1) {
                mine[j].push_back(i);
            }
        }
    }

    map<pair<int, int>, int> mp;
    for (int i = 0; i < m; i++) {
        mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    }

    for (int i = 0; i < q; i++) {
        auto rC = C;
        for (int e : x) rC[e] = INF;
        for (int e : mine[i]) {
            rC[x[e]] = 0;
            // cerr << "use: " << e << endl;
        }
        // cerr << "start" << endl;

        vector<vector<pair<int, ll>>> adj(n);
        for (int i = 0; i < m; i++) {
            adj[A[i]].emplace_back(B[i], rC[i]);
            adj[B[i]].emplace_back(A[i], rC[i]);
        }

        vector<int> par(n, -1);
        vector<ll> dist(n, INF);
        min_pq<pair<ll, int>> pq;
        pq.push({dist[0] = 0, 0});
        while (sz(pq)) {
            auto [d_c, c] = pq.top(); pq.pop();
            if (d_c != dist[c]) continue;
            for (auto [nxt, w] : adj[c]) {
                if (dist[nxt] > dist[c] + w) {
                    // cerr << "new_par: " << nxt << ' ' << c << endl;
                    par[nxt] = c;
                    pq.push({dist[nxt] = dist[c] + w, nxt});
                }
            }
        }

        // cerr << "building from: " << t[i] << endl;
        vector<int> ans{t[i]};
        while (ans.back() != 0) ans.push_back(par[ans.back()]);
        reverse(ans.begin(), ans.end());

        /*
        cerr << "nodes: ";
        for (int x : ans) cerr << x << ' ';
        cerr << endl;
        */

        vector<int> real;
        for (int i = 1; i < sz(ans); i++) real.push_back(mp[{ans[i-1], ans[i]}]);
        answer(real);

        // cerr << "done answer\n";
    }
}

Compilation message (stderr)

Aoi.cpp: In function 'll {anonymous}::cnt_less(int, int, int, const std::vector<int>&, std::map<int, int>&)':
Aoi.cpp:82:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   82 |         if ((rest >> p[i]) & 1 ^ 1) {
      |             ~~~~~~~~~~~~~~~^~~

Bitaro.cpp: In function 'void {anonymous}::build_need(const string&, int, int, int)':
Bitaro.cpp:40:9: warning: unused variable 'me' [-Wunused-variable]
   40 |     int me = 0;
      |         ^~
Bitaro.cpp:41:9: warning: unused variable 'cnt' [-Wunused-variable]
   41 |     int cnt = (r - l + 1) / 2 + 1;
      |         ^~~
Bitaro.cpp: In function 'll {anonymous}::get_cnt(std::vector<int>)':
Bitaro.cpp:74:57: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   74 |             for (int j = 0; j < q; j++) if ((mask >> j) & 1 ^ 1) {
      |                                             ~~~~~~~~~~~~^~~
Bitaro.cpp: At global scope:
Bitaro.cpp:31:4: warning: 'll {anonymous}::nck(int, int)' defined but not used [-Wunused-function]
   31 | ll nck(int n, int k) {
      |    ^~~
Bitaro.cpp:28:4: warning: '{anonymous}::memo_ways' defined but not used [-Wunused-variable]
   28 | ll memo_ways[3 * Q][3 * Q];
      |    ^~~~~~~~~

• Subtask 1: 99 / 100