제출 #1003004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003004		PurpleCrayon	Spy 3 (JOI24_spy3)	C++17	0 / 100	90 ms	138668 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];
    }

    // cerr << l << ' ' << r << ' ' << mask << endl;
    int who_peel = 0;
    for (int i = l; i <= r; i++) who_peel |= 1 << p[i];
    assert(peel.count(who_peel));
    int k = __builtin_popcount(peel[who_peel]);
    ll ans = 0;
    for (int i = mask; ; i = (i - 1) & mask) {
        if (__builtin_popcount(i) == k) {
            // 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) {
        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 __builtin_popcount(x) < __builtin_popcount(y);
    });

    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();
        int left = x;
        for (auto [y, v] : groups) {
            if ((y & x) == y) {
                use.push_back(v);

                if (left != y) peel[left] = y;
                left ^= y;
            } else {
                new_groups.push_back({y, v});
            }
        }

        assert(left == 0);

        sort(use.begin(), use.end());
        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) 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(ll n, ll k) { 
    return fact[n] / fact[k] / fact[n-k];
}

ll cnt_ways(int l, int r, const string& s) {
    int k = (r - l + 1) / 2 + 1;
    if (k == 1) return 1;
    if (memo_ways[l][r] != -1) return memo_ways[l][r];
    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            int one = (i-1 - l + 1) / 2 + 1;
            int two = sum - one;
            return memo_ways[l][r] = cnt_ways(l, i-1, s) * cnt_ways(i+1, r-1, s) * nck(one + two - 1, one - 1);
        }
    }
    assert(false);
}

vector<int> rec_perm(int l, int r, ll perm_idx, int mask, const string& s) {
    // cerr << "rec_perm: " << l << ' ' << r << ' ' << perm_idx << ' ' << mask << endl;
    int k = (r - l + 1) / 2 + 1;
    if (k == 1) {
        assert(perm_idx < __builtin_popcount(mask));
        int cnt = 0;
        for (int i = 0; ; i++) {
            if ((mask >> i) & 1) {
                if (cnt == perm_idx) return {i};
                cnt++;
            }
        }

        assert(false);
    }


    int sum = 0;
    for (int i = r; i >= l; i--) {
        if (s[i] == '1') sum++;
        else sum--;
        if (sum == 0) {
            int one = (i-1 - l + 1) / 2 + 1;
            int two = sum - one;
            ll his = cnt_ways(i+1, r-1, s);

            vector<int> one_part = rec_perm(l, i-1, perm_idx / his, mask, s);
            for (int x : one_part) mask ^= 1 << x;
            vector<int> two_part = rec_perm(i+1, r-1, perm_idx % his, mask, s);

            vector<int> ans;
            for (int x : one_part) ans.push_back(x);
            for (int x : two_part) ans.push_back(x);
            return ans;
        }
    }
    
    assert(false);
}

vector<int> build_perm(ll perm_idx, string s_tree) {
    int q = sz(s_tree) / 2 + 1;
    memset(memo_ways, -1, sizeof(memo_ways));
    return rec_perm(0, sz(s_tree)-1, perm_idx, (1 << q) - 1, s_tree);
}

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";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

Bitaro.cpp: In function 'std::vector<int> {anonymous}::rec_perm(int, int, ll, int, const string&)':
Bitaro.cpp:75:17: warning: unused variable 'two' [-Wunused-variable]
   75 |             int two = sum - one;
      |                 ^~~
Bitaro.cpp: In function 'll {anonymous}::cnt_ways(int, int, const string&)':
Bitaro.cpp:32:18: warning: array subscript -1 is below array bounds of 'll [17]' {aka 'long long int [17]'} [-Warray-bounds]
   32 |     return fact[n] / fact[k] / fact[n-k];
      |            ~~~~~~^
Bitaro.cpp:29:4: note: while referencing '{anonymous}::fact'
   29 | ll fact[Q+1];
      |    ^~~~

• Subtask 1: 0 / 100