| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003004 |
2024-06-20T00:40:43 Z |
PurpleCrayon |
Spy 3 (JOI24_spy3) |
C++17 |
|
90 ms |
138668 KB |
#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;
}
#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";
}
}
Compilation message
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];
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
138668 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
