結果
| 問題 | No.177 制作進行の宮森あおいです！ |
| ユーザー |
 penguin46
|
| 提出日時 | 2020-11-05 23:33:46 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 37 ms / 2,000 ms |
| コード長 | 38,545 bytes |
| コンパイル時間 | 2,163 ms |
| コンパイル使用メモリ | 157,316 KB |
| 実行使用メモリ | 73,676 KB |
| 最終ジャッジ日時 | 2024-07-22 11:37:36 |
| 合計ジャッジ時間 | 3,632 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 33 ms
73,372 KB |
| testcase_01 | AC | 32 ms
73,520 KB |
| testcase_02 | AC | 32 ms
73,508 KB |
| testcase_03 | AC | 33 ms
73,604 KB |
| testcase_04 | AC | 32 ms
73,432 KB |
| testcase_05 | AC | 35 ms
73,600 KB |
| testcase_06 | AC | 35 ms
73,676 KB |
| testcase_07 | AC | 35 ms
73,464 KB |
| testcase_08 | AC | 34 ms
73,532 KB |
| testcase_09 | AC | 33 ms
73,560 KB |
| testcase_10 | AC | 34 ms
73,600 KB |
| testcase_11 | AC | 35 ms
73,600 KB |
| testcase_12 | AC | 35 ms
73,560 KB |
| testcase_13 | AC | 37 ms
73,436 KB |
| testcase_14 | AC | 34 ms
73,520 KB |
| testcase_15 | AC | 35 ms
73,524 KB |
コンパイルメッセージ
main.cpp: In function 'll LSI(vll)':
main.cpp:409:1: warning: control reaches end of non-void function [-Wreturn-type]
409 | }
| ^
ソースコード
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <random>
//#include <atcoder/convolution>
//#include <atcoder/math>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/modint>
//#include <atcoder/scc>
//#include <atcoder/string>
//#include <atcoder/twosat>
//using namespace atcoder;
using namespace std;
// マクロ&定数&関数 ================================================
typedef int Int;
typedef int INt;
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;
typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<vector<vector<pll>>> vvvpll;
typedef vector<vector<vector<bool>>> vvvbool;
typedef vector<vector<vector<double>>> vvvdouble;
typedef vector<vector<vector<vector<double>>>> vvvvdouble;
const ll LLINF = 1e18 + 1;
const int DX[9] = { 0, 0, 1, -1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1, -1, 0, 0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const double PI = 3.14159265358979323846264338327950288;
const double EPS = 1e-7;
//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
const ll MOD = 1000000007; //10^9 + 7
//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } else return false; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } else return false; }
//---------------------------------------------------------------
// オーバーフローチェック
//---------------------------------------------------------------
bool is_overflow(ll a, ll b) {
ll M = numeric_limits<ll>::max();
return (a >= M / b);
}
//---------------------------------------------------------------
// 整数の乱数生成
//---------------------------------------------------------------
ll random_int(ll start, ll last) { return start + rand() % (last - start + 1); }
//---------------------------------------------------------------
// 2次元配列の表示(デバッグ用)
//---------------------------------------------------------------
template<class T>
void print2D(vector<vector<T>> A)
{
for (vector<T> aa : A) {
for (T a : aa)
cout << a << " ";
cout << endl;
}
cout << endl;
}
//---------------------------------------------------------------
// x∈[a, b)
//---------------------------------------------------------------
bool is_in(ll x, ll a, ll b) { return (a <= x && x < b); }
//---------------------------------------------------------------
// 文字系 → 整数
//---------------------------------------------------------------
ll to_int(string S) { return stoll(S); }
ll to_int(char c) { return int(c) - int('0'); }
ll to_int(const char *c) { return atoi(c); }
//---------------------------------------------------------------
// 2次元累積和 (ゼロパディング有り)
//---------------------------------------------------------------
template<class T>
vector<vector<T>> get_accum(vector<vector<T>> A)
{
T H = A.size();
T W = A[0].size();
vector<vector<T>> accum(H + 1, vector<T>(W + 1, 0));
for (int h = 0; h < H; h++)
for (int w = 0; w < W; w++)
accum[h + 1][w + 1] = A[h][w];
for (int h = 0; h <= H; h++)
for (int w = 0; w < W; w++)
accum[h][w + 1] += accum[h][w];
for (int h = 0; h < H; h++)
for (int w = 0; w <= W; w++)
accum[h + 1][w] += accum[h][w];
return accum;
}
//---------------------------------------------------------------
// 約数列挙 O(√N)
//---------------------------------------------------------------
vll divisor(ll n) {
vll ret;
for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } }
sort(begin(ret), end(ret)); return (ret);
}
//---------------------------------------------------------------
// N未満のすべての素数判定(エラトステネスの篩)
//---------------------------------------------------------------
vbool searchSosuu(ll N) {
vbool sosuu;
for (ll i = 0; i < N; i++) { sosuu.emplace_back(true); }
sosuu[0] = false; sosuu[1] = false;
for (ll i = 2; i < N; i++) { if (sosuu[i]) { for (ll j = 2; i * j < N; j++) { sosuu[i * j] = false; } } }
return sosuu;
}
//---------------------------------------------------------------
// 素因数分解 O(√N)
//---------------------------------------------------------------
vpll to_prime(ll n) {
vpll prime_factor;
for (ll i = 2; i * i <= n; i++) {
ll count = 0; while (n % i == 0) { count++; n /= i; }
if (count) { pair<ll, ll> temp = { i, count }; prime_factor.emplace_back(temp); }
}
if (n != 1) { pair<ll, ll> temp = { n, 1 }; prime_factor.emplace_back(temp); }
return prime_factor;
}
//---------------------------------------------------------------
// 高速素因数分解(前処理O(N), 分解O(logN))
//---------------------------------------------------------------
class FastPrime
{
public:
vll div; // i の約数のうちの1つ。
vbool is_sosuu; // i が素数であるか。
FastPrime(ll N) : div(N + 10, -1), is_sosuu(N + 10, true)
{
for (ll i = 2; i < N; i++)
if (div[i] == -1)
for (ll j = 2; i * j <= N; j++)
{
div[i * j] = i;
is_sosuu[i * j] = false;
}
}
vpll to_prime(ll N)
{
if (N == 1) return vpll({});
vll divs;
while (div[N] != -1)
{
divs.emplace_back(div[N]);
N /= div[N];
}
if (N > 1) divs.emplace_back(N);
sort(divs.begin(), divs.end());
vpll primes;
ll count = 1;
for (int i = 1; i < divs.size(); i++)
{
if (divs[i] > divs[i - 1])
{
primes.emplace_back(pll(divs[i - 1], count));
count = 0;
}
count++;
}
primes.emplace_back(pll(divs[divs.size() - 1], count));
return primes;
}
};
//---------------------------------------------------------------
// 最大公約数（ユークリッドの互除法）
//---------------------------------------------------------------
ll gcd(ll a, ll b) {
if (a < b) { ll tmp = a; a = b; b = tmp; }
ll r = a % b;
while (r != 0) { a = b; b = r; r = a % b; }
return b;
}
//---------------------------------------------------------------
// 約分
//---------------------------------------------------------------
pll reduce(ll a, ll b) {
ll g = gcd(a, b);
return pll(a / g, b / g);
}
//---------------------------------------------------------------
// 最小公倍数
//---------------------------------------------------------------
ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp * (a / temp) * (b / temp); }
//---------------------------------------------------------------
// 階乗
//---------------------------------------------------------------
ll factorial(ll n, ll mod = MOD) { if (n <= 1) { return 1; }return (n * (factorial(n - 1))) % mod; }
//---------------------------------------------------------------
// 高速コンビネーション計算(前処理:O(N) 計算:O(1))
//---------------------------------------------------------------
// テーブルを作る前処理
ll comb_const = 3000005;
vll fac(comb_const), finv(comb_const), inv(comb_const);
bool COMineted = false;
void COMinit(ll mod = MOD) {
fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1;
for (ll i = 2; i < comb_const; i++) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
COMineted = true;
}
// 二項係数計算
ll COM(ll n, ll k, ll mod = MOD) {
if (COMineted == false) COMinit(mod);
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return (fac[n] * (finv[k] * finv[n - k] % mod)) % mod;
}
//---------------------------------------------------------------
// 繰り返し２乗法 base^sisuu
//---------------------------------------------------------------
ll RepeatSquaring(ll base, ll sisuu, ll mod = MOD) {
if (sisuu < 0) { cout << "RepeatSquaring: 指数が負です!" << endl; return 0; }
if (sisuu == 0) return 1;
if (sisuu % 2 == 0) { ll t = RepeatSquaring(base, sisuu / 2, mod) % mod; return (t * t) % mod; }
return (base * RepeatSquaring(base, sisuu - 1, mod)) % mod;
}
//---------------------------------------------------------------
// 高速単発コンビネーション計算(O(logN))
//---------------------------------------------------------------
ll fast_com(ll a, ll b, ll mod = MOD) {
ll bunshi = 1; ll bunbo = 1;
for (ll i = 1; i <= b; i++) { bunbo *= i; bunbo %= mod; bunshi *= (a - i + 1); bunshi %= mod; }
ll ret = bunshi * RepeatSquaring(bunbo, mod - 2, mod); ret %= mod;
while (ret < 0) { ret += mod; }
return ret;
}
//---------------------------------------------------------------
// 整数をビットのリストに変換する ll->vbool
//---------------------------------------------------------------
vbool to_bitlist(ll bit, ll fixed_size = 1) {
if (bit == 0) return vbool(fixed_size, 0);
vbool list;
while (bit > 0) { list.emplace_back(bit & 1); bit /= 2; }
while (list.size() < fixed_size) { list.emplace_back(0); }
return list;
}
//---------------------------------------------------------------
// 立っているビットの数をカウントする
//---------------------------------------------------------------
ll bit_count(ll bit) {
ll ret = 0;
while (bit) {
ret += bit % 2;
bit /= 2;
}
return ret;
}
//---------------------------------------------------------------
// XORの階乗 0^1^...^N (O(1))
//---------------------------------------------------------------
ll xor_fac(ll N)
{
if (N == 0) return 0;
ll n_pair = (N - 1) / 2;
ll n_one = n_pair + 1;
if (n_pair * 2 + 1 == N) {
return n_one % 2;
}
else {
return (n_one % 2) ^ N;
}
}
//---------------------------------------------------------------
// 座標圧縮(O(NlogN)) 0スタートになることに注意！
//---------------------------------------------------------------
class PosPress
{
public:
vll pressed;
map<ll, ll> func; // 圧縮後を知りたい
map<ll, ll> rev; // 圧縮前を知りたい
PosPress(vll P) {
pressed = P; sort(P.begin(), P.end()); func[P[0]] = 0; rev[0] = P[0]; ll next = 1;
for (int i = 1; i < P.size(); i++) { if (P[i] != P[i - 1]) { func[P[i]] = next; rev[next] = P[i]; next++; } }
for (int i = 0; i < P.size(); i++) { pressed[i] = func[pressed[i]]; }
}
};
//---------------------------------------------------------------
// 行列積(O(N^3))
//---------------------------------------------------------------
vvll mat_cross(vvll A, vvll B) {
ll N = A.size(); ll K = B.size(); ll M = B[0].size();
vvll C(N, vll(M));
// 行列積の計算(+, * は |, & でもOK)
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < K; k++)
C[i][j] += A[i][k] * B[k][j];
return C;
}
//---------------------------------------------------------------
// 2直線の交差判定(直線(x1, y1)->(x2, y2) と 直線(X1, Y1)->(X2, Y2))
//---------------------------------------------------------------
bool is_cross(ll x1, ll y1, ll x2, ll y2, ll X1, ll Y1, ll X2, ll Y2) {
ll dx_ai = X1 - x1; ll dy_ai = Y1 - y1;
ll dx_bi = X1 - x2; ll dy_bi = Y1 - y2;
ll dx_ai2 = X2 - x1; ll dy_ai2 = Y2 - y1;
ll dx_bi2 = X2 - x2; ll dy_bi2 = Y2 - y2;
ll si = dx_ai * dy_bi - dy_ai * dx_bi;
ll si2 = dx_ai2 * dy_bi2 - dy_ai2 * dx_bi2;
ll si3 = dx_ai * dy_ai2 - dy_ai * dx_ai2;
ll si4 = dx_bi * dy_bi2 - dy_bi * dx_bi2;
return (si * si2 < 0 && si3 * si4 < 0);
}
//---------------------------------------------------------------
// 最長増加部分列の長さ(O(NlogN))
//---------------------------------------------------------------
ll LSI(vll vec)
{
ll size = vec.size();
vll lsi(size + 1, LLINF); // 長さjを作った時の右端の最小値
lsi[0] = 0; lsi[1] = vec[0];
for (ll i = 1; i < size; i++)
{
// 初めてvec[i]の方が小さくなるところを探す
auto Iter = lower_bound(lsi.begin(), lsi.end(), vec[i]);
ll idx = Iter - lsi.begin();
if (idx > 0 && lsi[idx - 1] < vec[i]) { lsi[idx] = vec[i]; }
}
for (ll i = size; i >= 0; i--) { if (lsi[i] < LLINF) { return i; } }
}
//---------------------------------------------------------------
// LCS(最長共通部分列) O(|S||T|)
//---------------------------------------------------------------
string LCS(string S, string T)
{
vvll dp(S.length() + 1);
for (int i = 0; i < dp.size(); i++) { vll t(T.length() + 1, 0); dp[i] = t; }
for (int i = 0; i < S.length(); i++) {
for (int j = 0; j < T.length(); j++) {
dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] });
}
}
ll len = dp[S.length()][T.length()];
string ans = "";
ll i = dp.size() - 1;
ll j = dp[0].size() - 1;
while (len > 0) {
if (dp[i - 1][j] == len) { i--; }
else if (dp[i][j - 1] == len) { j--; }
else { ans += S[i - 1]; i--; j--; len--; }
}
reverse(ans.begin(), ans.end());
return ans;
}
vll LCS(vll S, vll T)
{
vvll dp(S.size() + 1);
for (int i = 0; i < dp.size(); i++) { vll t(T.size() + 1, 0); dp[i] = t; }
for (int i = 0; i < S.size(); i++) {
for (int j = 0; j < T.size(); j++) {
dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] });
}
}
ll len = dp[S.size()][T.size()];
vll ans;
ll i = dp.size() - 1;
ll j = dp[0].size() - 1;
while (len > 0) {
if (dp[i - 1][j] == len) { i--; }
else if (dp[i][j - 1] == len) { j--; }
else { ans.emplace_back(S[i - 1]); i--; j--; len--; }
}
reverse(ans.begin(), ans.end());
return ans;
}
//---------------------------------------------------------------
// 木の根からの深さ
//---------------------------------------------------------------
vll tree_depth(vvll edge, ll root)
{
ll n_node = edge.size();
vll dist(n_node, LLINF);
dist[root] = 0;
stack<pll> S;
S.push({ root, 0 });
while (!S.empty())
{
ll node = S.top().first;
ll d = S.top().second;
dist[node] = d;
S.pop();
for (int i = 0; i < edge[node].size(); i++) {
if (dist[edge[node][i]] == LLINF) {
S.push({ edge[node][i], d + 1 });
}
}
}
return dist;
}
//---------------------------------------------------------------
// ワーシャルフロイド法(O(N^3)) d: 正方行列(N*N)
//---------------------------------------------------------------
vvll warshall_floyd(vvll d) {
ll n = d.size();
for (int k = 0; k < n; k++) { // 経由する頂点
for (int i = 0; i < n; i++) { // 始点
for (int j = 0; j < n; j++) { // 終点
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
return d;
}
//---------------------------------------------------------------
// Union Find
//---------------------------------------------------------------
class UnionFind {
private:
vll siz; // 素集合のサイズを表す配列(1 で初期化)
public:
ll n_group; // 集合の数
vll par; // 各元の親を表す配列
// Constructor
UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
n_group = sz_;
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
// Member Function
// Find
ll root(ll x) { // 根の検索
while (par[x] != x) {
x = par[x] = par[par[x]]; // x の親の親を x の親とする
}
return x;
}
// Union(Unite, Merge)
bool merge(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
// merge technique（データ構造をマージするテク．小を大にくっつける）
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
n_group--;
return true;
}
// 連結判定
bool issame(ll x, ll y) {
return root(x) == root(y);
}
// x を含むグループの大きさ
ll size(ll x) {
return siz[root(x)];
}
};
//---------------------------------------------------------------
// ダイクストラ(O(ElogV)) edge: 隣接リスト from->pair{to, cost}
//---------------------------------------------------------------
class Dijkstra
{
private:
vll past; // (iまで最短で行くときの一つ前)
public:
vll dist; // iまでの最短距離
// edge[i] -> {to, cost}
Dijkstra(vvpll edge, ll start) : dist(edge.size(), LLINF), past(edge.size(), -1)
{
using Pi = pll;
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
dist[start] = 0;
que.emplace(dist[start], start);
while (!que.empty()) {
ll cost;
int idx;
tie(cost, idx) = que.top();
que.pop();
if (dist[idx] < cost) continue;
for (int i = 0; i < edge[idx].size(); i++)
{
ll next_cost = cost + edge[idx][i].second;
if (dist[edge[idx][i].first] <= next_cost) continue;
dist[edge[idx][i].first] = next_cost;
past[edge[idx][i].first] = idx;
que.emplace(dist[edge[idx][i].first], edge[idx][i].first);
}
}
}
// goalまでの最短経路
vll shortest(ll goal)
{
vll ret;
while (goal != -1)
{
ret.emplace_back(goal);
goal = past[goal];
}
reverse(ret.begin(), ret.end());
return ret;
}
};
//---------------------------------------------------------------
// LCA: 最近共通祖先 (O())
//---------------------------------------------------------------
class Lca
{
private:
vvll doubling;
ll n_bit = 30;
public:
vll depth; // 根0からiまでの最短距離
// edge[i] -> {to, cost}
Lca(vvll edge, ll root = 0) : doubling(50, vll(edge.size(), -1))
{
// 深さ
depth = tree_depth(edge, root);
// ダブリングで親を辿れるようにする
// jから2^i回親を辿ったノード
doubling[0][0] = -1;
for (int i = 1; i < edge.size(); i++)
for (int j : edge[i])
if (depth[i] > depth[j]) { doubling[0][i] = j; break; }
for (int i = 1; i < n_bit; i++)
for (int j = 0; j < edge.size(); j++) {
if (doubling[i - 1][j] != -1) doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
else doubling[i][j] = -1;
}
}
// aとbの最近共通祖先
ll get_lca(ll a, ll b)
{
// depth[a] >= depth[b]にする
if (depth[a] < depth[b]) swap(a, b);
ll oa = a;
ll ob = b;
ll d = depth[a] - depth[b];
// aをdだけさかのぼる。
vbool bit = to_bitlist(d, n_bit);
for (int i = 0; i < n_bit; i++)if (bit[i]) a = doubling[i][a];
// depth[a] == depth[b]になっている。
for (int i = n_bit - 1; i >= 0; i--) {
if (doubling[i][a] == doubling[i][b]) continue;
a = doubling[i][a]; b = doubling[i][b];
}
return a == b ? a : doubling[0][a];
}
// パスの長さ
ll path_len(ll a, ll b)
{
return depth[a] + depth[b] - 2 * depth[get_lca(a, b)];
}
// パスに含まれる頂点集合
vll nodes_on_path(ll a, ll b)
{
if (a == b) return vll({ a });
vll ret;
ll lca = get_lca(a, b);
while (a != lca) {
ret.emplace_back(a);
a = doubling[0][a];
}
while (b != lca) {
ret.emplace_back(b);
b = doubling[0][b];
}
ret.emplace_back(lca);
return ret;
}
};
//---------------------------------------------------------------
// Z-algorithm(SとS[i:]の最長接頭辞長) O(|S|)
//---------------------------------------------------------------
vll Zalgorithm(string S)
{
ll n = S.size();
vll Z(n, 0);
ll start = -1;
ll last = -1;
for (ll i = 1; i < n; i++) {
if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); }
while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]])
Z[i] ++;
if (last < i + Z[i]) { last = i + Z[i]; start = i; }
}
Z[0] = n;
return Z;
}
vll Zalgorithm(vll S)
{
ll n = S.size();
vll Z(n, 0);
ll start = -1;
ll last = -1;
for (ll i = 1; i < n; i++) {
if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); }
while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]])
Z[i] ++;
if (last < i + Z[i]) { last = i + Z[i]; start = i; }
}
Z[0] = n;
return Z;
}
//---------------------------------------------------------------
// 二部グラフ判定(O(E)) edge -> リスト
//---------------------------------------------------------------
class Bipartite
{
private:
ll N;
public:
vll color; // 2色に塗り分けた時の塗り分け方
bool is_bipartite; // 2部グラフであるか
Bipartite(vvll edge) : color(edge.size(), -1)
{
N = edge.size();
color[0] = 0;
queue<ll> Q;
Q.push(0);
while (!Q.empty())
{
ll now = Q.front();
Q.pop();
for (int i : edge[now])
{
if (color[i] == -1)
{
color[i] = (color[now] == 0 ? 1 : 0);
Q.push(i);
}
else if (color[i] == color[now])
{
is_bipartite = false;
return;
}
}
}
is_bipartite = true;
}
};
//---------------------------------------------------------------
// ダブリング (行先のリスト, コスト) ← コストは任意
//---------------------------------------------------------------
class Doubling
{
private:
ll M = 100;
vvll doubling;
vvll cost;
bool have_cost = false;
public:
// to[i]: i から1回移動した先
// fee[i]: i から to[i]へと移動するコスト(任意)
Doubling(vll to, vll fee = {}) : doubling(M, vll(to.size(), -1)), cost(M, vll(to.size(), 0))
{
ll N = to.size();
have_cost = fee.size() > 0;
for (int i = 0; i < N; i++)
{
doubling[0][i] = to[i];
if (have_cost)
cost[0][i] = fee[i];
}
for (int i = 1; i < M; i++)
{
for (int j = 0; j < N; j++)
{
doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
if (have_cost)
cost[i][j] = cost[i - 1][j] + cost[i - 1][doubling[i - 1][j]];
}
}
}
// from から K 回移動した先
ll destination(ll from, ll K)
{
vbool bits = to_bitlist(K);
ll now = from;
ll sum = 0;
for (int i = 0; i < bits.size(); i++)
{
if (bits[i])
{
now = doubling[i][now];
}
}
return now;
}
// from から K 回移動するコストの合計
ll get_cost(ll from, ll K)
{
vbool bits = to_bitlist(K);
ll now = from;
ll sum = 0;
for (int i = 0; i < bits.size(); i++)
{
if (bits[i])
{
sum += cost[i][now];
now = doubling[i][now];
}
}
return sum;
}
};
//---------------------------------------------------------------
// ベルマンフォード(O(EV)) edge, from, to -> (cost, have_neg_roop)
//---------------------------------------------------------------
pair<ll, bool> BelmanFord(vvpll edge, ll from, ll to)
{
ll N = edge.size(); //頂点の数
vll d(N, LLINF); //始点から添え字の頂点に行くのにかかるコスト
d[from] = 0; //始点を0にする
bool have_negroop = false;
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
for (int k = 0; k < edge[j].size(); k++)
{
ll from = j;
ll to = edge[j][k].first;
ll cost = edge[j][k].second;
if (d[to] > d[from] + cost) { //移動した後のコストが小さいと、頂点のコストを更新
d[to] = d[from] + cost;
//頂点の数と同じ回数ループすると、負の閉路があるのでループをぬける
if (i == N - 1)
{
have_negroop = true;
break;
}
}
}
}
}
return pll(d[to], have_negroop);
}
//---------------------------------------------------------------
// ACL-最大流 (構築O(N), 更新・取得(N^2M))
//---------------------------------------------------------------
/*
<コンストラクタ> (n頂点)
mf_graph<ll> mf(int n);
<辺の追加> (O(1))
mf.add_edge(int from, int to, ll cap);
<最大流> O(n^2m)
mf.flow(int s, int t);
*/
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T &t) { payload.push_back(t); }
T &front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
} // namespace internal
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({ from, int(g[from].size()) });
int from_id = int(g[from].size());
int to_id = int(g[to].size());
if (from == to) to_id++;
g[from].push_back(_edge{ to, to_id, cap });
g[to].push_back(_edge{ from, from_id, 0 });
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{ pos[i].first, _e.to, _e.cap + _re.cap, _re.cap };
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = int(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto &_e = g[pos[i].first][pos[i].second];
auto &_re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int &i = iter[v]; i < int(g[v].size()); i++) {
_edge &e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) break;
}
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
while (flow < flow_limit) {
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
//---------------------------------------------------------------
// ACL-遅延セグ木(構築O(N), 更新・取得(logN))
//---------------------------------------------------------------
/*
<二分探索> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r)
seg.max_right<g>(int l);
<二分探索> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l)
seg.min_left<g>(int r);
bool g(S v) {
return V > v.value;
}
*/
template <class S, S(*op)(S, S), S(*e)(), class F, S(*mapping)(F, S), F(*composition)(F, F), F(*id)()>
struct lazy_segtree {
private:
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
// モノイドの型
//struct S {
// ll value; // 値
// int size; // 区間の大きさ
//};
//
//// 写像の定義(data部分に用いる関数, 区間の合成)
//S op(S l, S r) { return S{ max(l.value, r.value), l.size + r.size }; }
//
//// 単位元
//S e() { return S{ 0, 0 }; }
//
//// F(x) (遅延評価するときの関数・加算or代入, lazyのretへの当て方)
//S mapping(ll f, S x) { return S{ max(x.value, f), x.size }; }
//
//// 作用素(lazy同士)の合成
//ll composition(ll l, ll r) { return max(l, r); }
//
//// lazyの単位元
//ll id() { return 0; }
//
//// 二分探索の関数
//ll V;
//bool g(S v) {
// return V > v.value;
//}
int main() {
//////==================================
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(25);
//////==================================
/*
～思いついたことはとりあえず絶対メモする！！～
～オーバーフローに注意！！！～
*/
ll W;
cin >> W;
ll N, M;
cin >> N;
vll A(N);
for (int i = 0; i < N; i++)
{
cin >> A[i];
}
cin >> M;
mf_graph<ll> mf(N + M + 2);
for(int i = 0;i<N;i++)
{
mf.add_edge(0, i + 1, A[i]);
}
vll B(M);
for (int i = 0; i < M; i++)
{
cin >> B[i];
mf.add_edge(N + 1 + i, N + M + 1, B[i]);
}
vvbool can(N, vbool(M, true));
for (int i = 0; i < M; i++)
{
ll Q;
cin >> Q;
for (int q = 0; q < Q; q++)
{
ll x;
cin >> x;
x--;
can[x][i] = false;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if(can[i][j])
mf.add_edge(i + 1, N + 1 + j, LLINF);
}
}
cout << (mf.flow(0, N + M + 1) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
}