| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1003040 | PurpleCrayon | Spy 3 (JOI24_spy3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 = 30;
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;
}