QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#636700 | #9249. Elimination Series Once More | maspy | TL | 1768ms | 33592kb | C++20 | 26.5kb | 2024-10-13 02:06:37 | 2024-10-13 02:06:37 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
(check(x) ? ok : ng) = x;
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
vc<T> &res = first;
(res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io.hpp"
#define FASTIO
#include <unistd.h>
// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
if (pir < SZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
void rd(char &c) {
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
}
void rd(string &x) {
x.clear();
char c;
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
do {
x += c;
if (pil == pir) load();
c = ibuf[pil++];
} while (!isspace(c));
}
template <typename T>
void rd_real(T &x) {
string s;
rd(s);
x = stod(s);
}
template <typename T>
void rd_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (minus) x = -x;
}
}
void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }
template <class T, class U>
void rd(pair<T, U> &p) {
return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd(x);
rd_tuple<N + 1>(t);
}
}
template <class... T>
void rd(tuple<T...> &tpl) {
rd_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
for (auto &d: x) rd(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
void wt(const char c) {
if (por == SZ) flush();
obuf[por++] = c;
}
void wt(const string s) {
for (char c: s) wt(c);
}
void wt(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) wt(s[i]);
}
template <typename T>
void wt_integer(T x) {
if (por > SZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <typename T>
void wt_real(T x) {
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
wt(s);
}
void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }
template <class T, class U>
void wt(const pair<T, U> val) {
wt(val.first);
wt(' ');
wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt(' '); }
const auto x = std::get<N>(t);
wt(x);
wt_tuple<N + 1>(t);
}
}
template <class... T>
void wt(tuple<T...> tpl) {
wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
template <class T>
void wt(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;
#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
#line 1 "/home/maspy/compro/library/ds/bit_vector.hpp"
struct Bit_Vector {
int n;
bool prepared = 0;
vc<pair<u64, u32>> dat;
Bit_Vector(int n) : n(n) { dat.assign((n + 127) >> 6, {0, 0}); }
void set(int i) {
assert(!prepared);
dat[i >> 6].fi |= u64(1) << (i & 63);
}
void reset() {
fill(all(dat), pair<u64, u32>{0, 0});
prepared = 0;
}
void build() {
prepared = 1;
FOR(i, len(dat) - 1) dat[i + 1].se = dat[i].se + popcnt(dat[i].fi);
}
// [0, k) 内の 1 の個数
bool operator[](int i) { return dat[i >> 6].fi >> (i & 63) & 1; }
int count_prefix(int k, bool f = true) {
assert(prepared);
auto [a, b] = dat[k >> 6];
int ret = b + popcnt(a & ((u64(1) << (k & 63)) - 1));
return (f ? ret : k - ret);
}
int count(int L, int R, bool f = true) { return count_prefix(R, f) - count_prefix(L, f); }
string to_string() {
string ans;
FOR(i, n) ans += '0' + (dat[i / 64].fi >> (i % 64) & 1);
return ans;
}
};
#line 1 "/home/maspy/compro/library/ds/index_compression.hpp"
template <typename T>
struct Index_Compression_DISTINCT_SMALL {
static_assert(is_same_v<T, int>);
int mi, ma;
vc<int> dat;
vc<int> build(vc<int> X) {
mi = 0, ma = -1;
if (!X.empty()) mi = MIN(X), ma = MAX(X);
dat.assign(ma - mi + 2, 0);
for (auto& x: X) dat[x - mi + 1]++;
FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
for (auto& x: X) { x = dat[x - mi]++; }
FOR_R(i, 1, len(dat)) dat[i] = dat[i - 1];
dat[0] = 0;
return X;
}
int operator()(ll x) { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
};
template <typename T>
struct Index_Compression_SAME_SMALL {
static_assert(is_same_v<T, int>);
int mi, ma;
vc<int> dat;
vc<int> build(vc<int> X) {
mi = 0, ma = -1;
if (!X.empty()) mi = MIN(X), ma = MAX(X);
dat.assign(ma - mi + 2, 0);
for (auto& x: X) dat[x - mi + 1] = 1;
FOR(i, len(dat) - 1) dat[i + 1] += dat[i];
for (auto& x: X) { x = dat[x - mi]; }
return X;
}
int operator()(ll x) { return dat[clamp<ll>(x - mi, 0, ma - mi + 1)]; }
};
template <typename T>
struct Index_Compression_SAME_LARGE {
vc<T> dat;
vc<int> build(vc<T> X) {
vc<int> I = argsort(X);
vc<int> res(len(X));
for (auto& i: I) {
if (!dat.empty() && dat.back() == X[i]) {
res[i] = len(dat) - 1;
} else {
res[i] = len(dat);
dat.eb(X[i]);
}
}
dat.shrink_to_fit();
return res;
}
int operator()(T x) { return LB(dat, x); }
};
template <typename T>
struct Index_Compression_DISTINCT_LARGE {
vc<T> dat;
vc<int> build(vc<T> X) {
vc<int> I = argsort(X);
vc<int> res(len(X));
for (auto& i: I) { res[i] = len(dat), dat.eb(X[i]); }
dat.shrink_to_fit();
return res;
}
int operator()(T x) { return LB(dat, x); }
};
template <typename T, bool SMALL>
using Index_Compression_DISTINCT =
typename std::conditional<SMALL, Index_Compression_DISTINCT_SMALL<T>,
Index_Compression_DISTINCT_LARGE<T>>::type;
template <typename T, bool SMALL>
using Index_Compression_SAME =
typename std::conditional<SMALL, Index_Compression_SAME_SMALL<T>,
Index_Compression_SAME_LARGE<T>>::type;
// SAME: [2,3,2] -> [0,1,0]
// DISTINCT: [2,2,3] -> [0,2,1]
// (x): lower_bound(X,x) をかえす
template <typename T, bool SAME, bool SMALL>
using Index_Compression =
typename std::conditional<SAME, Index_Compression_SAME<T, SMALL>,
Index_Compression_DISTINCT<T, SMALL>>::type;
#line 2 "/home/maspy/compro/library/alg/monoid/add.hpp"
template <typename E>
struct Monoid_Add {
using X = E;
using value_type = X;
static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
static constexpr X inverse(const X &x) noexcept { return -x; }
static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
static constexpr X unit() { return X(0); }
static constexpr bool commute = true;
};
#line 4 "/home/maspy/compro/library/ds/wavelet_matrix/wavelet_matrix.hpp"
// 静的メソッドinverseの存在をチェックするテンプレート
template <typename, typename = std::void_t<>>
struct has_inverse : std::false_type {};
template <typename T>
struct has_inverse<T, std::void_t<decltype(T::inverse(std::declval<typename T::value_type>()))>> : std::true_type {};
struct Dummy_Data_Structure {
using MX = Monoid_Add<bool>;
void build(const vc<bool>& A) {}
};
template <typename Y, bool SMALL_Y, typename SEGTREE = Dummy_Data_Structure>
struct Wavelet_Matrix {
using Mono = typename SEGTREE::MX;
using T = typename Mono::value_type;
static_assert(Mono::commute);
int n, log, K;
Index_Compression<Y, true, SMALL_Y> IDX;
vc<Y> ItoY;
vc<int> mid;
vc<Bit_Vector> bv;
vc<SEGTREE> seg;
Wavelet_Matrix() {}
Wavelet_Matrix(const vc<Y>& A) { build(A); }
Wavelet_Matrix(const vc<Y>& A, vc<T>& SUM_Data) { build(A, SUM_Data); }
template <typename F>
Wavelet_Matrix(int n, F f) {
build(n, f);
}
template <typename F>
void build(int m, F f) {
vc<Y> A(m);
vc<T> S(m);
for (int i = 0; i < m; ++i) tie(A[i], S[i]) = f(i);
build(A, S);
}
void build(const vc<Y>& A) { build(A, vc<T>(len(A), Mono::unit())); }
void build(const vc<Y>& A, vc<T> S) {
n = len(A);
vc<int> B = IDX.build(A);
K = 0;
for (auto& x: B) chmax(K, x + 1);
ItoY.resize(K);
FOR(i, n) ItoY[B[i]] = A[i];
log = 0;
while ((1 << log) < K) ++log;
mid.resize(log), bv.assign(log, Bit_Vector(n));
vc<int> B0(n), B1(n);
vc<T> S0(n), S1(n);
seg.resize(log + 1);
seg[log].build(S);
for (int d = log - 1; d >= 0; --d) {
int p0 = 0, p1 = 0;
for (int i = 0; i < n; ++i) {
bool f = (B[i] >> d & 1);
if (!f) { B0[p0] = B[i], S0[p0] = S[i], p0++; }
if (f) { bv[d].set(i), B1[p1] = B[i], S1[p1] = S[i], p1++; }
}
swap(B, B0), swap(S, S0);
move(B1.begin(), B1.begin() + p1, B.begin() + p0);
move(S1.begin(), S1.begin() + p1, S.begin() + p0);
mid[d] = p0, bv[d].build(), seg[d].build(S);
}
}
// [L,R) x [0,y)
int prefix_count(int L, int R, Y y) {
int p = IDX(y);
if (L == R || p == 0) return 0;
if (p == K) return R - L;
int cnt = 0;
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
if (p >> d & 1) cnt += r0 - l0, L = l1, R = r1;
if (!(p >> d & 1)) L = l0, R = r0;
}
return cnt;
}
// [L,R) x [y1,y2)
int count(int L, int R, Y y1, Y y2) { return prefix_count(L, R, y2) - prefix_count(L, R, y1); }
// [L,R) x [0,y)
pair<int, T> prefix_count_and_prod(int L, int R, Y y) {
int p = IDX(y);
if (p == 0) return {0, Mono::unit()};
if (p == K) return {R - L, seg[log].prod(L, R)};
int cnt = 0;
T t = Mono::unit();
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
if (p >> d & 1) { cnt += r0 - l0, t = Mono::op(t, seg[d].prod(l0, r0)), L = l1, R = r1; }
if (!(p >> d & 1)) L = l0, R = r0;
}
return {cnt, t};
}
// [L,R) x [y1,y2)
pair<int, T> count_and_prod(int L, int R, Y y1, Y y2) {
if constexpr (has_inverse<Mono>::value) {
auto [c1, t1] = prefix_count_and_prod(L, R, y1);
auto [c2, t2] = prefix_count_and_prod(L, R, y2);
return {c2 - c1, Mono::op(Mono::inverse(t1), t2)};
}
int lo = IDX(y1), hi = IDX(y2), cnt = 0;
T t = Mono::unit();
auto dfs = [&](auto& dfs, int d, int L, int R, int a, int b) -> void {
assert(b - a == (1 << d));
if (hi <= a || b <= lo) return;
if (lo <= a && b <= hi) {
cnt += R - L, t = Mono::op(t, seg[d].prod(L, R));
return;
}
--d;
int c = (a + b) / 2;
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
dfs(dfs, d, l0, r0, a, c), dfs(dfs, d, l1, r1, c, b);
};
dfs(dfs, log, L, R, 0, 1 << log);
return {cnt, t};
}
// [L,R) x [y1,y2)
T prefix_prod(int L, int R, Y y) { return prefix_count_and_prod(L, R, y).se; }
// [L,R) x [y1,y2)
T prod(int L, int R, Y y1, Y y2) { return count_and_prod(L, R, y1, y2).se; }
T prod_all(int L, int R) { return seg[log].prod(L, R); }
Y kth(int L, int R, int k) {
assert(0 <= k && k < R - L);
int p = 0;
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
if (k < r0 - l0) {
L = l0, R = r0;
} else {
k -= r0 - l0, L = l1, R = r1, p |= 1 << d;
}
}
return ItoY[p];
}
// y 以上最小 OR infty<Y>
Y next(int L, int R, Y y) {
int k = IDX(y);
int p = K;
auto dfs = [&](auto& dfs, int d, int L, int R, int a, int b) -> void {
if (p <= a || L == R || b <= k) return;
if (d == 0) {
chmin(p, a);
return;
}
--d;
int c = (a + b) / 2;
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
dfs(dfs, d, l0, r0, a, c), dfs(dfs, d, l1, r1, c, b);
};
dfs(dfs, log, L, R, 0, 1 << log);
return (p == K ? infty<Y> : ItoY[p]);
}
// y 以下最大 OR -infty<T>
Y prev(int L, int R, Y y) {
int k = IDX(y + 1);
int p = -1;
auto dfs = [&](auto& dfs, int d, int L, int R, int a, int b) -> void {
if (b - 1 <= p || L == R || k <= a) return;
if (d == 0) {
chmax(p, a);
return;
}
--d;
int c = (a + b) / 2;
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
dfs(dfs, d, l1, r1, c, b), dfs(dfs, d, l0, r0, a, c);
};
dfs(dfs, log, L, R, 0, 1 << log);
return (p == -1 ? -infty<Y> : ItoY[p]);
}
Y median(bool UPPER, int L, int R) {
assert(0 <= L && L < R && R <= n);
int k = (UPPER ? (R - L) / 2 : (R - L - 1) / 2);
return kth(L, R, k);
}
pair<Y, T> kth_value_and_prod(int L, int R, int k) {
assert(0 <= k && k <= R - L);
if (k == R - L) return {infty<Y>, seg[log].prod(L, R)};
int p = 0;
T t = Mono::unit();
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
if (k < r0 - l0) {
L = l0, R = r0;
} else {
t = Mono::op(t, seg[d].prod(l0, r0)), k -= r0 - l0, L = l1, R = r1, p |= 1 << d;
}
}
t = Mono::op(t, seg[0].prod(L, L + k));
return {ItoY[p], t};
}
T prod_index_range(int L, int R, int k1, int k2) {
static_assert(has_inverse<Mono>::value);
T t1 = kth_value_and_prod(L, R, k1).se;
T t2 = kth_value_and_prod(L, R, k2).se;
return Mono::op(Mono::inverse(t1), t2);
}
// [L,R) x [0,y) での check(cnt, prod) が true となる最大の (cnt,prod)
template <typename F>
pair<int, T> max_right(F check, int L, int R) {
int cnt = 0;
T t = Mono::unit();
assert(check(0, Mono::unit()));
if (check(R - L, seg[log].prod(L, R))) { return {R - L, seg[log].prod(L, R)}; }
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
int cnt1 = cnt + r0 - l0;
T t1 = Mono::op(t, seg[d].prod(l0, r0));
if (check(cnt1, t1)) {
cnt = cnt1, t = t1, L = l1, R = r1;
} else {
L = l0, R = r0;
}
}
return {cnt, t};
}
void set(int i, T t) {
assert(0 <= i && i < n);
int L = i, R = i + 1;
seg[log].set(L, t);
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
if (l0 < r0) L = l0, R = r0;
if (l0 == r0) L = l1, R = r1;
seg[d].set(L, t);
}
}
void multiply(int i, T t) {
assert(0 <= i && i < n);
int L = i, R = i + 1;
seg[log].multiply(L, t);
for (int d = log - 1; d >= 0; --d) {
int l0 = bv[d].count_prefix(L, 0), r0 = bv[d].count_prefix(R, 0);
int l1 = L + mid[d] - l0, r1 = R + mid[d] - r0;
if (l0 < r0) L = l0, R = r0;
if (l0 == r0) L = l1, R = r1;
seg[d].multiply(L, t);
}
}
void add(int i, T t) { multiply(i, t); }
};
#line 5 "main.cpp"
void solve() {
LL(N, K);
VEC(int, A, 1 << N);
for (auto& x: A) --x;
Wavelet_Matrix<int, 1> WM(A);
vc<int> ANS(1 << N);
FOR(n, 1, N + 1) {
// 2^n 人
FOR(b, (1 << N) / (1 << n)) {
int L = b << n, R = (b + 1) << n;
FOR(i, L, R) {
if (ANS[i] < n - 1) continue;
int x = A[i];
if (x < (1 << n) - 1) continue;
int cnt = WM.count(L, R, x + 1, 1 << N);
if (cnt <= K) ANS[i] = n;
}
}
}
print(ANS);
}
signed main() { solve(); }
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3680kb
input:
2 1 1 2 3 4
output:
0 1 1 2
result:
ok 4 number(s): "0 1 1 2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
3 5 2 4 7 5 3 8 6 1
output:
1 2 2 2 1 3 2 0
result:
ok 8 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
3 0 1 2 7 4 5 8 3 6
output:
0 1 2 0 0 3 0 1
result:
ok 8 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
3 5 3 7 1 2 4 8 5 6
output:
1 2 0 1 2 3 2 2
result:
ok 8 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
3 3 3 4 8 2 7 6 1 5
output:
1 2 3 1 2 2 0 2
result:
ok 8 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
3 3 4 2 6 8 3 5 1 7
output:
2 1 2 3 1 2 0 2
result:
ok 8 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
3 4 5 8 1 3 2 4 6 7
output:
2 3 0 1 1 2 2 2
result:
ok 8 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
3 1 7 3 8 6 5 2 4 1
output:
2 1 3 1 2 1 2 0
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
3 4 1 2 5 3 6 7 4 8
output:
0 1 2 1 2 2 2 3
result:
ok 8 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
3 2 2 4 8 6 3 7 5 1
output:
1 2 3 2 1 2 2 0
result:
ok 8 numbers
Test #11:
score: 0
Accepted
time: 3ms
memory: 3704kb
input:
10 780 495 929 348 345 426 543 187 419 839 812 320 1018 251 284 944 258 721 640 730 528 316 247 313 195 809 948 261 615 805 213 388 894 1005 77 599 636 881 444 144 923 240 520 592 465 96 455 563 943 237 860 531 269 106 989 740 506 23 224 84 475 108 718 3 16 731 436 591 627 672 300 573 613 253 637 46...
output:
8 9 8 8 8 9 7 8 9 9 8 9 7 8 9 8 9 9 9 9 8 7 8 7 9 9 8 9 9 7 8 9 9 6 9 9 9 8 7 9 7 9 9 8 6 8 9 9 7 9 9 8 6 9 9 8 4 7 6 8 6 9 1 4 9 8 9 9 9 8 9 9 7 9 8 9 9 9 6 7 6 7 9 9 9 9 9 7 6 8 8 8 9 9 6 6 9 9 9 8 9 9 6 9 9 8 6 7 8 8 3 8 8 9 6 9 7 8 8 9 9 9 9 8 7 9 8 8 7 7 9 9 9 9 9 8 8 9 6 9 9 9 9 9 9 6 9 8 8 9 ...
result:
ok 1024 numbers
Test #12:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
10 175 10 301 861 580 539 53 822 97 923 133 952 870 438 265 55 825 557 784 976 584 993 897 981 259 875 18 106 399 1019 692 336 485 491 9 565 114 738 128 678 23 562 538 869 787 768 385 494 640 655 666 332 930 798 418 801 266 1009 846 54 37 967 139 394 802 168 503 233 848 340 329 240 898 251 1023 779 ...
output:
3 7 9 8 8 5 9 6 9 7 9 9 8 7 5 9 8 9 9 8 9 9 9 7 9 4 6 8 9 9 8 8 8 3 8 6 9 7 9 4 8 8 9 9 9 8 8 8 8 8 8 9 9 8 9 7 9 9 5 5 9 7 8 9 7 8 7 9 8 8 7 9 7 9 9 9 8 8 9 9 8 7 9 7 8 6 8 5 5 9 9 7 8 9 6 5 8 9 8 5 7 8 9 7 6 9 8 9 8 2 6 9 8 9 9 8 8 5 9 8 9 7 9 9 9 6 9 9 7 10 9 8 9 9 9 7 8 7 8 8 8 6 7 6 7 4 8 9 9 8...
result:
ok 1024 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
10 15 829 331 590 799 39 456 888 779 60 411 796 148 678 930 101 653 81 429 4 457 455 703 780 260 251 21 291 122 366 177 665 326 114 96 445 123 154 340 522 113 895 170 144 857 447 865 874 891 679 541 867 731 436 219 871 596 285 1008 435 263 881 798 16 275 14 97 845 269 974 782 343 404 561 540 443 482...
output:
6 4 5 6 4 5 7 5 4 4 6 4 5 7 4 5 4 5 2 5 5 5 6 4 4 4 4 4 4 4 5 4 4 4 4 4 4 4 5 4 7 4 4 6 5 6 7 7 5 5 6 5 4 4 6 5 4 9 4 4 7 6 4 4 3 4 6 4 8 6 4 4 5 5 4 5 7 7 4 4 4 4 4 5 9 4 4 7 5 8 4 4 6 4 6 9 6 4 8 5 5 4 4 4 5 4 5 5 4 4 4 4 5 4 5 5 4 5 4 4 5 4 4 6 4 9 5 6 8 6 5 6 6 7 4 4 4 4 4 4 4 3 4 4 4 4 6 7 7 5 ...
result:
ok 1024 numbers
Test #14:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
10 215 910 367 1011 675 689 697 604 665 730 306 743 225 210 1008 546 439 411 475 529 640 54 505 420 481 213 406 1012 933 392 121 751 554 265 550 621 537 212 908 49 918 768 125 16 927 507 863 1000 44 900 7 645 543 784 461 569 669 984 249 189 727 497 994 719 282 666 691 58 795 119 515 682 150 53 494 6...
output:
9 8 9 9 9 9 9 9 9 8 9 7 7 9 8 8 8 8 8 9 5 8 8 8 7 8 9 9 8 6 9 8 8 8 9 8 7 9 5 9 9 6 4 9 8 9 9 5 9 2 9 8 9 8 8 9 9 7 7 9 8 9 9 8 9 9 5 9 6 8 9 7 5 8 9 8 9 9 7 9 8 9 9 9 8 9 7 5 8 7 9 8 8 6 9 9 8 6 5 9 8 8 9 8 7 9 9 8 6 4 9 6 9 8 8 9 7 8 9 8 5 8 8 9 8 9 8 9 9 8 8 7 5 9 9 9 9 9 8 8 9 9 6 8 6 8 6 9 9 9 ...
result:
ok 1024 numbers
Test #15:
score: 0
Accepted
time: 2ms
memory: 4000kb
input:
10 358 714 252 544 999 507 766 720 169 379 856 698 40 910 610 564 125 278 426 285 205 746 43 23 284 81 525 848 540 827 604 630 741 27 313 452 724 9 745 762 263 44 901 864 445 418 596 310 719 988 536 799 625 202 895 412 153 847 145 353 297 133 260 717 893 158 314 90 356 108 315 1016 510 1015 1007 747...
output:
9 7 9 9 8 9 9 7 8 9 9 5 9 9 9 6 8 8 8 7 9 5 4 8 6 9 9 9 9 9 9 9 4 8 8 9 3 9 9 8 5 9 9 8 8 9 8 9 9 9 9 9 7 9 8 7 9 7 8 8 7 8 9 9 7 8 6 8 6 8 9 8 9 9 9 7 9 9 7 9 6 9 9 7 8 7 9 7 8 7 9 9 7 9 9 4 8 9 8 9 9 9 7 9 6 9 8 9 9 9 8 9 9 9 8 3 8 9 4 7 8 8 8 8 8 8 9 6 8 6 9 7 9 9 8 7 9 9 9 9 7 8 9 8 9 8 9 7 8 9 ...
result:
ok 1024 numbers
Test #16:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
10 409 720 603 348 938 361 756 506 176 661 192 318 599 115 548 681 692 915 148 721 93 424 707 404 392 695 342 247 799 743 814 82 120 365 428 461 355 184 372 224 810 225 569 630 800 480 226 802 867 136 592 723 412 248 619 817 67 891 72 74 315 624 250 1001 73 536 397 859 553 647 143 575 733 468 298 71...
output:
9 9 8 9 8 9 8 7 9 7 8 9 6 9 9 9 9 7 9 6 8 9 8 8 9 8 7 9 9 9 6 6 8 8 8 8 7 8 7 9 7 9 9 9 8 7 9 9 7 9 9 8 7 9 9 6 9 6 6 8 9 7 9 6 9 8 9 9 9 7 9 9 8 8 9 6 9 9 8 9 9 9 7 8 8 9 5 9 7 7 7 9 9 9 8 7 8 9 8 8 8 8 4 8 8 9 9 8 6 9 9 9 2 9 7 9 8 9 8 7 8 7 9 6 6 9 9 9 7 9 9 8 9 9 9 9 8 9 8 8 8 9 9 9 8 9 6 9 8 9 ...
result:
ok 1024 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 700 469 249 763 385 977 949 423 11 825 442 744 993 553 908 410 860 465 291 751 234 50 897 64 346 481 1010 444 88 605 268 531 167 853 367 389 191 784 723 783 277 916 649 418 932 516 972 714 905 358 364 334 293 391 337 785 837 721 568 555 102 456 554 165 141 253 852 43 109 699 963 915 611 16 156 83...
output:
8 7 9 8 9 9 8 3 9 8 9 9 9 9 8 9 8 8 9 7 5 9 6 8 8 9 8 6 9 8 9 7 9 8 8 7 9 9 9 8 9 9 8 9 9 9 9 9 8 8 8 8 8 8 9 9 9 9 9 6 8 9 7 7 7 9 5 6 9 9 9 9 4 7 6 8 9 9 9 7 6 5 8 8 9 8 8 8 9 7 8 9 8 8 7 9 7 9 6 6 8 9 5 9 9 8 9 8 9 9 9 8 9 8 8 9 7 9 8 6 8 6 9 9 6 9 9 5 8 7 8 9 8 8 9 6 7 7 9 8 9 9 9 9 9 6 9 9 7 6 ...
result:
ok 1024 numbers
Test #18:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
10 655 971 111 296 479 453 490 163 686 195 492 1014 762 1021 15 351 618 137 181 853 758 876 598 703 486 125 35 41 266 603 682 733 294 391 967 373 508 860 501 1018 1003 642 365 531 883 89 674 869 311 442 734 886 165 701 139 447 271 540 190 983 474 816 769 1015 101 896 904 692 627 643 750 615 20 406 5...
output:
9 6 8 8 8 8 7 9 7 8 9 9 9 3 8 9 7 7 9 9 9 9 9 8 6 5 5 8 9 9 9 8 8 9 8 8 9 8 9 9 9 8 9 9 6 9 9 8 8 9 9 7 9 7 8 8 9 7 9 8 9 9 9 6 9 9 9 9 9 9 9 4 8 8 7 8 7 9 9 8 2 9 9 9 9 9 9 5 8 7 9 9 7 8 8 6 7 7 7 8 9 9 9 9 9 7 9 9 9 5 9 9 7 7 9 9 8 9 7 6 7 8 9 8 4 9 8 9 9 9 8 9 8 8 9 5 8 7 4 9 9 9 6 8 8 9 8 9 9 8 ...
result:
ok 1024 numbers
Test #19:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
10 827 692 816 52 570 178 260 248 531 852 777 232 378 955 632 325 256 328 599 802 165 966 493 166 125 488 942 965 716 947 276 156 894 194 742 933 185 384 152 277 333 991 424 487 435 423 504 113 106 307 205 745 155 654 226 16 518 884 757 1009 133 401 392 451 510 682 717 922 608 148 206 854 355 728 51...
output:
9 9 5 9 7 8 7 9 9 9 7 8 9 9 8 8 8 9 9 7 9 8 7 6 8 9 9 9 9 8 7 9 7 9 9 7 8 7 8 8 9 8 8 8 8 8 6 6 8 7 9 7 9 7 4 9 9 9 9 7 8 8 8 8 9 9 9 9 7 7 9 8 9 8 7 7 5 7 8 9 8 8 8 9 9 7 9 6 9 8 6 6 4 9 8 5 9 6 9 9 7 9 9 6 9 9 8 8 9 9 9 9 9 9 8 2 6 9 9 9 7 8 9 9 2 8 7 8 8 8 7 9 9 8 9 8 4 9 9 8 9 8 8 9 4 8 9 9 9 6 ...
result:
ok 1024 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 3984kb
input:
10 328 454 408 810 540 254 321 33 682 91 53 398 761 1023 243 581 545 825 892 100 356 17 326 487 878 787 756 996 707 770 924 945 272 428 686 339 908 390 645 238 337 517 364 717 404 533 394 849 435 894 947 482 806 657 39 781 946 75 656 129 476 676 984 456 412 463 160 562 592 345 141 145 501 921 991 21...
output:
8 8 9 9 7 8 5 9 6 5 8 9 9 7 9 9 9 9 6 8 4 8 8 9 9 9 9 9 9 9 9 8 8 9 8 9 8 9 7 8 9 8 9 8 9 8 9 8 9 9 8 9 9 5 9 9 6 9 7 8 9 9 8 8 8 7 9 9 8 7 7 8 9 9 7 8 6 5 9 9 3 9 9 6 9 9 6 9 1 9 9 8 8 8 8 8 8 9 8 9 8 5 8 9 7 9 8 7 8 9 9 8 8 2 9 7 8 9 7 9 8 9 9 9 8 8 9 9 9 8 9 6 7 9 9 8 8 9 7 9 9 9 9 9 9 9 9 4 6 9 ...
result:
ok 1024 numbers
Test #21:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
10 825 601 142 625 471 287 405 117 857 340 984 863 530 575 994 436 394 529 25 141 332 735 966 1 831 673 896 89 272 649 81 384 242 864 817 174 382 145 469 577 715 893 275 914 455 667 169 179 521 305 925 976 213 40 380 659 499 918 725 561 616 948 924 1022 721 235 485 85 781 540 52 892 982 254 461 381 ...
output:
9 7 9 8 8 8 6 9 8 9 9 9 9 9 8 8 9 4 7 8 9 9 0 9 9 9 6 8 9 6 8 7 9 9 7 8 7 8 9 9 9 8 9 8 9 7 7 9 8 9 9 7 5 8 9 8 9 9 9 9 9 9 9 9 7 8 6 9 9 5 9 9 7 8 8 9 9 6 9 9 9 9 8 4 5 7 9 9 8 5 9 9 9 7 9 6 8 9 2 6 9 8 9 7 7 9 9 9 9 9 9 7 8 8 9 9 9 6 9 8 7 9 9 6 9 9 9 4 9 8 9 9 9 8 7 8 7 8 7 8 9 8 4 9 9 9 6 7 7 9 ...
result:
ok 1024 numbers
Test #22:
score: 0
Accepted
time: 1739ms
memory: 33364kb
input:
20 0 179487 921757 700836 1026745 871114 487101 416568 943369 555729 702080 475044 257810 489454 716476 879881 237658 884615 645342 654881 754504 537330 488794 60810 581898 627225 134547 267586 35544 535278 202909 1006004 182486 863804 12271 705426 1000913 315415 495258 494119 323180 59354 347058 62...
output:
0 1 0 5 1 0 0 2 0 2 1 0 0 1 3 0 3 0 0 1 1 0 0 2 2 0 1 0 1 0 4 0 1 0 0 3 0 2 1 0 0 1 0 2 1 0 6 0 4 0 0 1 0 1 0 2 2 0 0 1 0 3 0 1 4 0 0 1 2 0 0 1 0 1 0 3 0 1 2 0 2 0 1 0 3 0 0 1 1 0 12 0 2 0 1 0 0 1 4 0 0 1 2 0 0 3 0 1 0 1 0 2 1 0 2 0 0 1 3 0 0 1 0 5 0 1 2 0 1 0 0 3 1 0 0 2 1 0 4 0 2 0 0 1 1 0 2 0 0 5...
result:
ok 1048576 numbers
Test #23:
score: 0
Accepted
time: 1768ms
memory: 33488kb
input:
20 0 423991 752898 398498 684927 789044 263019 482251 912839 731501 161924 299043 221772 386164 726231 81052 522548 2147 664063 669633 811292 646801 487230 645801 231433 697608 767873 119403 655574 294512 625240 464604 171777 37789 989183 13473 24697 1013507 285860 816836 313163 256565 724812 246357...
output:
0 2 0 1 1 0 0 5 3 0 1 0 0 2 0 1 0 1 0 4 2 0 1 0 0 3 0 1 0 2 1 0 0 2 0 1 3 0 1 0 0 2 1 0 0 1 0 6 4 0 1 0 0 2 0 1 1 0 0 3 1 0 0 2 0 1 2 0 0 3 1 0 0 5 1 0 0 1 2 0 2 0 1 0 1 0 4 0 0 3 0 1 2 0 1 0 0 1 3 0 2 0 0 1 8 0 0 1 1 0 2 0 1 0 0 3 0 1 2 0 4 0 1 0 0 2 1 0 6 0 1 0 1 0 2 0 1 0 0 2 1 0 3 0 0 1 0 4 2 0 ...
result:
ok 1048576 numbers
Test #24:
score: 0
Accepted
time: 1760ms
memory: 33572kb
input:
20 0 983530 824894 353093 559444 613542 519778 1010412 455455 935622 219374 221225 1002197 688110 472174 221344 689249 527925 36045 510374 449980 724144 993684 416271 594751 888484 336792 425268 493926 392740 391689 841678 822738 12764 433848 349413 450603 182285 354617 758953 176599 70237 340919 10...
output:
2 0 0 1 1 0 6 0 1 0 0 3 1 0 0 2 2 0 1 0 0 4 0 1 3 0 0 1 1 0 2 0 0 1 0 2 0 1 4 0 0 1 0 3 0 1 0 2 0 3 0 1 1 0 2 0 0 5 0 1 0 2 0 1 1 0 2 0 0 1 0 4 1 0 0 2 0 1 0 3 0 2 1 0 7 0 1 0 0 3 1 0 0 1 2 0 0 1 2 0 1 0 0 4 0 2 0 1 1 0 0 3 0 2 0 1 0 1 0 3 0 5 1 0 1 0 2 0 4 0 0 1 0 2 0 1 2 0 1 0 3 0 1 0 1 0 6 0 0 2 ...
result:
ok 1048576 numbers
Test #25:
score: 0
Accepted
time: 1744ms
memory: 33592kb
input:
20 0 473443 822631 836606 745020 669384 831958 929557 812459 979454 261979 335172 118201 544502 229223 877541 915721 504368 226689 582157 166448 910835 805293 989769 735782 836472 212234 901652 203944 246343 341883 923372 761793 496413 774045 10709 822705 804842 393237 234688 760980 575433 264037 29...
output:
0 1 2 0 0 1 3 0 4 0 1 0 1 0 0 2 1 0 2 0 1 0 5 0 1 0 2 0 0 1 3 0 0 1 0 3 2 0 0 1 1 0 0 6 2 0 0 1 0 1 0 2 0 1 0 3 1 0 2 0 0 4 0 1 0 1 8 0 2 0 1 0 1 0 0 3 2 0 0 1 0 1 0 3 0 2 1 0 2 0 0 1 1 0 0 4 1 0 3 0 1 0 2 0 2 0 0 1 4 0 0 1 2 0 1 0 1 0 3 0 0 2 1 0 0 1 5 0 2 0 1 0 0 4 1 0 3 0 0 1 1 0 0 2 0 6 0 1 2 0 ...
result:
ok 1048576 numbers
Test #26:
score: 0
Accepted
time: 1749ms
memory: 33480kb
input:
20 0 379980 596897 473700 685210 871737 592347 265581 99773 654162 711671 796026 221716 77951 211806 1016499 68541 105291 832026 37890 741817 787 338525 847057 564452 291439 25137 796527 274136 516811 336906 65693 431115 565546 913432 505987 731031 411514 962171 317881 69424 7338 181350 326333 89987...
output:
0 1 0 2 3 0 1 0 0 1 2 0 0 1 5 0 0 2 0 1 0 1 4 0 1 0 3 0 2 0 0 1 0 2 0 1 0 4 1 0 0 1 0 3 1 0 2 0 0 6 0 1 2 0 1 0 0 1 2 0 0 3 1 0 0 3 1 0 0 1 2 0 0 2 0 1 4 0 1 0 0 3 0 1 2 0 1 0 1 0 0 2 1 0 5 0 2 0 0 1 1 0 4 0 0 1 0 3 2 0 1 0 1 0 0 2 1 0 3 0 0 1 2 0 1 0 0 8 0 3 1 0 0 2 1 0 1 0 0 2 5 0 1 0 0 1 0 2 1 0 ...
result:
ok 1048576 numbers
Test #27:
score: -100
Time Limit Exceeded
input:
20 966077 920272 22829 905052 391939 529694 220017 113245 305146 1033496 776070 372388 649193 372732 578999 535089 376914 300958 674096 713438 294435 185108 175377 843411 186645 326129 937577 777304 855769 317353 63291 166972 152975 982092 882338 296632 371732 94559 247688 915006 853946 1012694 9336...