QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#311914 | #4255. Sone2 | hos_lyric# | 50 | 113ms | 33252kb | C++14 | 20.2kb | 2024-01-22 23:33:32 | 2024-07-04 03:21:21 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
// SA-IS
// String: string, vector<int>, vector<long long>
// if sigma <= n, O(n) time, O(n) space
// if sigma > n, O(n log n) time, O(n) space
template <class String> vector<int> suffixArrayRec(const String &as) {
const int n = as.size();
if (n == 0) return {};
const auto minmaxA = minmax_element(as.begin(), as.end());
const auto minA = *minmaxA.first, maxA = *minmaxA.second;
if (static_cast<unsigned long long>(maxA) - minA >=
static_cast<unsigned long long>(n)) {
vector<int> us(n);
for (int u = 0; u < n; ++u) us[u] = u;
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (as[u] < as[v]);
});
int b = 0;
vector<int> bs(n, 0);
for (int i = 1; i < n; ++i) {
if (as[us[i - 1]] != as[us[i]]) ++b;
bs[us[i]] = b;
}
return suffixArrayRec(bs);
}
const int sigma = maxA - minA + 1;
vector<int> pt(sigma + 1, 0), poss(sigma);
for (int u = 0; u < n; ++u) ++pt[as[u] - minA + 1];
for (int a = 0; a < sigma; ++a) pt[a + 1] += pt[a];
// cmp[u] := (as[u, n) < as[u + 1, n))
vector<bool> cmp(n);
cmp[n - 1] = false;
for (int u = n - 1; --u >= 0; ) {
cmp[u] = (as[u] != as[u + 1]) ? (as[u] < as[u + 1]) : cmp[u + 1];
}
// ><, nn - id (0 <= id < n)
int nn = 0;
vector<int> ids(n, 0);
int last = n;
vector<int> nxt(n, 0);
// put ><, from the tail of each bucket
vector<int> us(n, 0);
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int u = n - 1; --u >= 1; ) if (!cmp[u - 1] && cmp[u]) {
ids[u] = ++nn;
nxt[u] = last;
last = u;
us[--poss[as[u] - minA]] = u;
}
// follow > backwards, from the head of each bucket
memcpy(poss.data(), pt.data(), sigma * sizeof(int));
us[poss[as[n - 1] - minA]++] = n - 1;
for (int i = 0; i < n; ++i) {
const int u = us[i];
if (u && !cmp[u - 1]) us[poss[as[u - 1] - minA]++] = u - 1;
}
// follow < backwards, from the tail of each bucket
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int i = n; --i >= 0; ) {
const int u = us[i];
if (u && cmp[u - 1]) us[--poss[as[u - 1] - minA]] = u - 1;
}
if (nn) {
int vsLen = 0;
vector<int> vs(nn);
for (const int u : us) if (ids[u]) vs[vsLen++] = u;
int b = 0;
vector<int> bs(nn, 0);
for (int j = 1; j < nn; ++j) {
// as[v1, w1] (< or =) as[v0, w0]
int v1 = vs[j - 1], v0 = vs[j];
const int w1 = nxt[v1], w0 = nxt[v0];
if (w1 - v1 != w0 - v0) {
++b;
} else {
for (; ; ++v1, ++v0) {
if (v1 == n) { ++b; break; }
if (as[v1] != as[v0]) { ++b; break; }
if (v1 == w1) break;
}
}
bs[nn - ids[vs[j]]] = b;
}
for (int u = 0; u < n; ++u) if (ids[u]) vs[nn - ids[u]] = u;
const auto sub = suffixArrayRec(bs);
// put ><, from the tail of each bucket
memset(us.data(), 0, n * sizeof(int));
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int j = nn; --j >= 0; ) {
const int u = vs[sub[j]];
us[--poss[as[u] - minA]] = u;
}
// follow > backwards, from the head of each bucket
memcpy(poss.data(), pt.data(), sigma * sizeof(int));
us[poss[as[n - 1] - minA]++] = n - 1;
for (int i = 0; i < n; ++i) {
const int u = us[i];
if (u && !cmp[u - 1]) us[poss[as[u - 1] - minA]++] = u - 1;
}
// follow < backwards, from the tail of each bucket
memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
for (int i = n; --i >= 0; ) {
const int u = us[i];
if (u && cmp[u - 1]) us[--poss[as[u - 1] - minA]] = u - 1;
}
}
return us;
}
// us[i]: i-th suffix
// su[u]: index of as[u, n)
// hs[i]: longest common prefix of as[us[i - 1], n) and as[us[i], n)
struct SuffixArray {
int n;
bool rmq;
vector<int> us, su, hs, bsr;
SuffixArray() : n(0), rmq(false) {}
SuffixArray(const string &as, bool rmq_) : rmq(rmq_) { build(as); }
SuffixArray(const vector<int> &as, bool rmq_) : rmq(rmq_) { build(as); }
SuffixArray(const vector<long long> &as, bool rmq_) : rmq(rmq_) { build(as); }
template <class String> void build(const String &as) {
n = as.size();
us = suffixArrayRec(as);
su.resize(n + 1);
for (int i = 0; i < n; ++i) su[us[i]] = i;
su[n] = -1;
hs.assign(n, 0);
for (int h = 0, u = 0; u < n; ++u) if (su[u]) {
for (int v = us[su[u] - 1]; v + h < n && as[v + h] == as[u + h]; ++h) {}
hs[su[u]] = h;
if (h) --h;
}
if (rmq) {
const int logN = n ? (31 - __builtin_clz(n)) : 0;
hs.resize((logN + 1) * n - (1 << logN) + 1);
for (int e = 0; e < logN; ++e) {
int *hes = hs.data() + e * n;
for (int i = 0; i <= n - (1 << (e + 1)); ++i) {
hes[n + i] = min(hes[i], hes[i + (1 << e)]);
}
}
bsr.resize(n + 1);
bsr[0] = -1;
for (int i = 1; i <= n; ++i) bsr[i] = bsr[i >> 1] + 1;
}
}
// Returns longest common prefix of as[u, n) and as[v, n).
// 0 <= u, v <= n
// Assumes rmq.
inline int lcp(int u, int v) const {
if (u == v) return n - u;
int i = su[u], j = su[v];
if (i > j) swap(i, j);
const int e = bsr[j - i];
return min(hs[e * n + i + 1], hs[e * n + j + 1 - (1 << e)]);
}
};
////////////////////////////////////////////////////////////////////////////////
// zs[i] := lcp(as[0, n), as[i, n))
// 0 i-j j i
// |-------| |-------| zs[j]
// |---| |---| |---| |---| zs[i-j]
template <class T> void suffixZ(const T *as, int n, int *zs) {
if (n == 0) return;
zs[0] = 0;
for (int j = 0, i = 1; i < n; ++i) {
if (i + zs[i - j] < j + zs[j]) {
zs[i] = zs[i - j];
} else {
int &z = zs[i] = max(j + zs[j] - i, 0);
for (; i + z < n && as[z] == as[i + z]; ++z) {}
j = i;
}
}
zs[0] = n;
}
template <class T> vector<int> suffixZ(const T &as) {
vector<int> zs(as.size());
suffixZ(as.data(), as.size(), zs.data());
return zs;
}
////////////////////////////////////////////////////////////////////////////////
template <class X, class Y, class T> struct StaticPointAddRectSum {
struct Rect {
X x0, x1;
Y y0, y1;
};
vector<pair<X, Y>> as;
vector<Rect> bs;
vector<T> vals, anss;
// Adds val to (x, y).
void add(X x, Y y, const T &val) {
as.emplace_back(x, y);
vals.push_back(val);
}
// Gets sum of [x0, x1) * [y0, y1).
// ~~> Gets (x*, y*)
void get(X x0, X x1, Y y0, Y y1) {
assert(x0 <= x1); assert(y0 <= y1);
bs.push_back(Rect{x0, x1, y0, y1});
}
void run() {
const int asLen = as.size(), bsLen = bs.size();
// same x ==> get then add
vector<pair<X, int>> events((bsLen << 1) + asLen);
for (int i = 0; i < asLen; ++i) {
events[(bsLen << 1) + i] = std::make_pair(as[i].first, (bsLen << 1) + i);
}
for (int j = 0; j < bsLen; ++j) {
events[j << 1 ] = std::make_pair(bs[j].x0, j << 1 );
events[j << 1 | 1] = std::make_pair(bs[j].x1, j << 1 | 1);
}
std::sort(events.begin(), events.end());
vector<Y> ys(asLen);
for (int i = 0; i < asLen; ++i) {
ys[i] = as[i].second;
}
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
const int ysLen = ys.size();
vector<T> bit(ysLen, 0);
anss.assign(bsLen, 0);
for (const auto &event : events) {
if (event.second >= bsLen << 1) {
const int i = event.second - (bsLen << 1);
for (int l = std::lower_bound(ys.begin(), ys.end(), as[i].second) - ys.begin(); l < ysLen; l |= l + 1) {
bit[l] += vals[i];
}
} else {
const int j = event.second >> 1;
T sum = 0;
for (int l = std::lower_bound(ys.begin(), ys.end(), bs[j].y0) - ys.begin(); l > 0; l &= l - 1) {
sum -= bit[l - 1];
}
for (int l = std::lower_bound(ys.begin(), ys.end(), bs[j].y1) - ys.begin(); l > 0; l &= l - 1) {
sum += bit[l - 1];
}
(event.second & 1) ? (anss[j] += sum) : (anss[j] -= sum);
}
}
}
};
////////////////////////////////////////////////////////////////////////////////
// T: monoid representing information of an interval.
// T() should return the identity.
// T(S s) should represent a single element of the array.
// T::pull(const T &l, const T &r) should pull two intervals.
template <class T> struct SegmentTreePoint {
int logN, n;
vector<T> ts;
SegmentTreePoint() : logN(0), n(0) {}
explicit SegmentTreePoint(int n_) {
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
}
template <class S> explicit SegmentTreePoint(const vector<S> &ss) {
const int n_ = ss.size();
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
build();
}
T &at(int i) {
return ts[n + i];
}
void build() {
for (int u = n; --u; ) pull(u);
}
inline void pull(int u) {
ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
}
// Changes the value of point a to s.
template <class S> void change(int a, const S &s) {
assert(0 <= a); assert(a < n);
ts[a += n] = T(s);
for (; a >>= 1; ) pull(a);
}
// Applies T::f(args...) to point a.
template <class F, class... Args>
void ch(int a, F f, Args &&... args) {
assert(0 <= a); assert(a < n);
(ts[a += n].*f)(args...);
for (; a >>= 1; ) pull(a);
}
// Calculates the product for [a, b).
T get(int a, int b) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return T();
a += n; b += n;
T prodL, prodR, t;
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) { t.pull(prodL, ts[aa++]); prodL = t; }
if (bb & 1) { t.pull(ts[--bb], prodR); prodR = t; }
}
t.pull(prodL, prodR);
return t;
}
// Calculates T::f(args...) of a monoid type for [a, b).
// op(-, -) should calculate the product.
// e() should return the identity.
template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
auto
#else
decltype((std::declval<T>().*F())())
#endif
get(int a, int b, Op op, E e, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return e();
a += n; b += n;
auto prodL = e(), prodR = e();
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...));
if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR);
}
return op(prodL, prodR);
}
// Find min b s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from left to right.
// Returns n + 1 if there is no such b.
template <class F, class... Args>
int findRight(int a, F f, Args &&... args) {
assert(0 <= a); assert(a <= n);
if ((T().*f)(args...)) return a;
if (a == n) return n + 1;
a += n;
for (; ; a >>= 1) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < n; ) {
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - n + 1;
}
++a;
if (!(a & (a - 1))) return n + 1;
}
}
// Find max a s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from right to left.
// Returns -1 if there is no such a.
template <class F, class... Args>
int findLeft(int b, F f, Args &&... args) {
assert(0 <= b); assert(b <= n);
if ((T().*f)(args...)) return b;
if (b == 0) return -1;
b += n;
for (; ; b >>= 1) if ((b & 1) || b == 2) {
if ((ts[b - 1].*f)(args...)) {
for (; b <= n; ) {
if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
}
return b - n - 1;
}
--b;
if (!(b & (b - 1))) return -1;
}
}
};
////////////////////////////////////////////////////////////////////////////////
constexpr int INF = 1001001001;
struct NodeCountMax {
int mx, lz;
int cnt;
NodeCountMax() : mx(-INF), lz(0), cnt(0) {}
NodeCountMax(int val) : mx(val), lz(0), cnt(1) {}
void push(NodeCountMax &l, NodeCountMax &r) {
if (lz) {
l.add(lz);
r.add(lz);
lz = 0;
}
}
void pull(const NodeCountMax &l, const NodeCountMax &r) {
if (l.mx > r.mx) {
mx = l.mx;
cnt = l.cnt;
} else if (l.mx < r.mx) {
mx = r.mx;
cnt = r.cnt;
} else {
mx = l.mx;
cnt = l.cnt + r.cnt;
}
}
void add(int val) {
mx += val;
lz += val;
}
// leaf
void change(int val) {
mx = val;
cnt = 1;
}
};
int ID;
int ALen, BLen;
vector<int> A, B;
int Q;
vector<int> O, Y, Z, Y2, Z2;
SuffixArray saB, saRevB;
namespace brute {
vector<pair<int, int>> run() {
vector<pair<int, int>> ans(Q, make_pair(-1, -1));
auto as = A;
#define A do_not_use_A
for (int q = 0; q < Q; ++q) {
switch (O[q]) {
case 1: {
as[Y[q]] = Z[q];
for (int i = 0; i < ALen; ++i) {
int l = 0;
for (; i + l < ALen && l < BLen && as[i + l] == B[l]; ++l) {}
if (chmax(ans[q].first, l)) ans[q].second = 0;
if (ans[q].first == l) ++ans[q].second;
}
// cerr<<as<<" "<<B<<": "<<ans[q]<<endl;
} break;
case 2: {
for (int i = Y[q]; i < Z[q]; ++i) {
int l = 0;
for (; i + l < Z[q] && l < BLen && as[i + l] == B[l]; ++l) {}
if (chmax(ans[q].first, l)) ans[q].second = 0;
if (ans[q].first == l) ++ans[q].second;
}
} break;
case 3: {
int l = 0;
for (; Y[q] + l < BLen && Z[q] + l < BLen && B[Y[q] + l] == B[Z[q] + l]; ++l) {}
ans[q].first = l;
} break;
case 4: {
vector<int> cat;
cat.insert(cat.end(), B.begin() + Y[q], B.begin() + Z[q]);
cat.insert(cat.end(), B.begin() + Y2[q], B.begin() + Z2[q]);
const int catLen = cat.size();
ans[q].first = 0;
for (int i = 0; i + catLen <= BLen; ++i) {
bool ok = true;
for (int j = 0; j < catLen; ++j) if (B[i + j] != cat[j]) {
ok = false;
break;
}
if (ok) {
++ans[q].first;
}
}
} break;
default: assert(false);
}
}
#undef A
return ans;
}
} // brute
vector<int> solve3() {
vector<int> ans(Q, -1);
for (int q = 0; q < Q; ++q) if (O[q] == 3) {
ans[q] = saB.lcp(Y[q], Z[q]);
}
return ans;
}
vector<int> solve4() {
StaticPointAddRectSum<int, int, int> f;
for (int i = 1; i < BLen; ++i) {
f.add(saRevB.su[BLen - i], saB.su[i], +1);
}
#define saB do_not_use_saB
#define saRevB do_not_use_saRevB
// jL <= j < jR <=> [l, r) matches [sa.us[j], *)
auto sub = [&](const SuffixArray &sa, int l, int r) -> pair<int, int> {
pair<int, int> ret;
{
int lo = -1, hi = sa.su[l];
for (; lo + 1 < hi; ) {
const int mid = (lo + hi) / 2;
((sa.lcp(sa.us[mid], l) >= r - l) ? hi : lo) = mid;
}
ret.first = hi;
}
{
int lo = sa.su[l], hi = sa.n;
for (; lo + 1 < hi; ) {
const int mid = (lo + hi) / 2;
((sa.lcp(l, sa.us[mid]) >= r - l) ? lo : hi) = mid;
}
ret.second = hi;
}
return ret;
};
#undef saB
#undef saRevB
for (int q = 0; q < Q; ++q) if (O[q] == 4) {
const auto res1 = sub(saRevB, BLen - Z[q], BLen - Y[q]);
const auto res2 = sub(saB, Y2[q], Z2[q]);
f.get(res1.first, res1.second, res2.first, res2.second);
}
f.run();
vector<int> ans(Q, 0);
int pos = 0;
for (int q = 0; q < Q; ++q) if (O[q] == 4) {
ans[q] = f.anss[pos++];
}
return ans;
}
namespace slow {
vector<int> as;
vector<int> fs;
SegmentTreePoint<NodeCountMax> seg;
void init() {
as = A;
auto B0A = B;
B0A.push_back(0);
B0A.insert(B0A.end(), A.begin(), A.end());
const auto zs = suffixZ(B0A);
fs.resize(ALen);
seg = SegmentTreePoint<NodeCountMax>(ALen);
for (int i = 0; i < ALen; ++i) {
seg.at(i) = fs[i] = zs[BLen + 1 + i];
}
seg.build();
}
#define A do_not_use_A
void block(int pos) {
for (int i = max(pos - BLen + 1, 0); i <= pos; ++i) {
if (chmin(fs[i], pos - i)) {
seg.change(i, fs[i]);
}
}
}
void allow(int pos) {
const int i0 = max(pos - BLen + 1, 0);
auto b0a = B;
b0a.push_back(0);
b0a.insert(b0a.end(), as.begin() + i0, as.begin() + min(pos + BLen, ALen));
const auto zs = suffixZ(b0a);
for (int i = i0; i <= pos; ++i) {
const int f = zs[BLen + 1 + i - i0];
if (fs[i] != f) {
seg.change(i, fs[i] = f);
}
}
}
pair<int, int> get(int l, int r) {
const auto res = seg.get(l, r);
return make_pair(res.mx, res.cnt);
}
#undef A
vector<pair<int, int>> run() {
vector<pair<int, int>> ans(Q, make_pair(-1, -1));
init();
for (int q = 0; q < Q; ++q) {
if (O[q] == 1) {
if (as[Y[q]] != Z[q]) {
block(Y[q]);
as[Y[q]] = Z[q];
allow(Y[q]);
}
ans[q] = get(0, ALen);
} else if (O[q] == 2) {
if (Z[q] < ALen) block(Z[q]);
ans[q] = get(Y[q], Z[q]);
if (Z[q] < ALen) allow(Z[q]);
}
}
{
const auto res = solve3();
for (int q = 0; q < Q; ++q) if (O[q] == 3) ans[q].first = res[q];
}
{
const auto res = solve4();
for (int q = 0; q < Q; ++q) if (O[q] == 4) ans[q].first = res[q];
}
return ans;
}
} // slow
int main() {
for (; ~scanf("%d", &ID); ) {
scanf("%d", &ALen);
A.resize(ALen);
for (int i = 0; i < ALen; ++i) scanf("%d", &A[i]);
scanf("%d", &BLen);
B.resize(BLen);
for (int i = 0; i < BLen; ++i) scanf("%d", &B[i]);
scanf("%d", &Q);
O.assign(Q, -1);
Y.assign(Q, -1);
Z.assign(Q, -1);
Y2.assign(Q, -1);
Z2.assign(Q, -1);
for (int q = 0; q < Q; ++q) {
scanf("%d%d%d", &O[q], &Y[q], &Z[q]);
switch (O[q]) {
case 1: {
--Y[q];
} break;
case 2: {
--Y[q];
} break;
case 3: {
--Y[q];
--Z[q];
} break;
case 4: {
scanf("%d%d", &Y2[q], &Z2[q]);
--Y[q];
--Y2[q];
} break;
default: assert(false);
}
}
auto revB = B;
reverse(revB.begin(), revB.end());
saB = SuffixArray(B, true);
saRevB = SuffixArray(revB, true);
const auto ans = slow::run();
for (int q = 0; q < Q; ++q) {
switch (O[q]) {
case 1: case 2: {
printf("%d %d\n", ans[q].first, ans[q].second);
} break;
case 3: {
printf("%d\n", ans[q].first);
} break;
case 4: {
puts(ans[q].first ? "yes" : "no");
} break;
default: assert(false);
}
}
#ifdef LOCAL
const auto brt=brute::run();
assert(brt==ans);
#endif
}
return 0;
}
详细
Test #1:
score: 5
Accepted
time: 1ms
memory: 3892kb
input:
1 1000 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 299 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 824 1...
output:
46 1 12 2 46 1 46 1 73 1 100 1 51 1 100 1 100 1 73 1 0 73 1 73 1 73 1 73 1 73 1 19 1 51 1 73 1 73 1 73 1 44 1 51 1 51 1 73 1 22 2 73 1 46 1 0 73 1 yes 57 1 73 1 73 1 73 1 73 1 73 1 73 1 73 1 73 1 51 1 yes 73 1 51 1 73 1 30 1 73 1 73 1 15 1 73 1 73 1 73 1 73 1 46 1 73 1 65 1 0 73 1 12 1 3 1 73 1 73 1...
result:
ok 1911 tokens
Test #2:
score: 5
Accepted
time: 1ms
memory: 3972kb
input:
2 1000 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 406 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 98 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 970 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 ...
output:
62 1 93 1 62 3 93 1 62 2 65 1 93 1 93 1 93 1 93 1 93 1 62 2 1 93 1 93 1 62 2 62 2 62 3 42 1 93 1 93 1 62 2 44 1 93 1 62 2 93 1 62 1 93 1 72 1 72 1 62 1 72 1 23 1 72 1 no 62 2 72 1 72 1 72 1 62 3 72 1 72 1 72 1 no 43 1 72 1 62 2 40 1 62 2 8 1 62 2 62 2 0 62 2 62 1 62 1 62 1 62 2 62 2 62 1 62 2 5 62 1...
result:
ok 1915 tokens
Test #3:
score: 5
Accepted
time: 25ms
memory: 11100kb
input:
3 100000 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1...
output:
100 979 100 978 4 100 978 100 977 100 976 100 975 100 974 100 973 100 972 100 971 100 971 100 970 100 969 100 968 100 967 100 966 100 966 100 965 100 965 9 100 964 no 100 964 100 963 100 962 100 961 100 960 100 959 100 958 100 957 100 956 100 955 yes 100 954 100 954 100 953 100 952 100 951 100 950 1...
result:
ok 191356 tokens
Test #4:
score: 5
Accepted
time: 25ms
memory: 11116kb
input:
4 100000 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1...
output:
100 979 100 978 100 977 100 976 100 975 100 974 100 974 100 973 no 100 972 100 971 100 970 100 970 100 969 100 968 100 967 100 966 no 100 965 100 964 100 963 100 962 100 961 100 960 100 959 100 959 0 100 958 100 957 100 957 100 957 100 956 100 955 100 954 100 953 0 100 952 2 100 951 100 950 100 950 ...
result:
ok 191356 tokens
Test #5:
score: 5
Accepted
time: 48ms
memory: 11288kb
input:
5 100000 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3...
output:
30 3312 30 1774 30 3311 30 2286 0 30 365 30 3310 30 3309 30 3308 30 3307 30 3306 30 3305 30 1856 30 387 30 1033 30 3304 30 1681 30 3303 30 3302 30 3302 30 3301 30 3300 30 845 30 544 30 2719 30 3299 30 1344 30 3298 30 3298 yes 30 3297 30 3296 30 3295 30 473 30 3294 30 3293 30 3292 yes 30 859 30 3291 ...
result:
ok 191359 tokens
Test #6:
score: 5
Accepted
time: 63ms
memory: 11056kb
input:
6 100000 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2...
output:
30 33114 30 12379 30 33114 30 33104 30 23307 30 33094 30 33084 30 1497 no 30 33074 30 13431 30 33064 30 19 30 33054 30 33044 30 4288 30 10728 30 33034 30 6847 30 33024 30 10621 30 33014 30 10308 1 30 11959 30 3935 30 19153 30 33004 30 32994 30 2789 30 32984 30 32984 0 30 21909 30 32984 30 10889 30 3...
result:
ok 191357 tokens
Test #7:
score: 5
Accepted
time: 58ms
memory: 29388kb
input:
7 100000 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1 0 1 4 1 5 1 12 2 7 3 4 4 0 0 1 0 1 3 2 2 2 1 3 0 3 2 3 2 7 0 2 1 1 3 78193 0 5 2 8 7 10 4 4 2 1 0 0 1 1 9 0 1 2 1 7 10 0 0 0 6 0 0 4 7 4 3 1 2 0 0 1 12 2 0 2 5 3 1 0 3 4 7 1 0 9 4 1 5 2 6 23 0 12 6 6 0 2 8 4 2 5 2 1 0 3 10 8 0 2 5 1 2 6 5 9 1 0 0 9 4 3 0 5 0 0 6 4 4 0 1 3 13 0 2 4 1 5 2 0 5 4 2 1 ...
result:
ok 100000 tokens
Test #8:
score: 5
Accepted
time: 57ms
memory: 29460kb
input:
8 100000 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0 8 5 2 0 8 4 8 1 2 0 2 0 1 9 1 0 0 0 2 2 0 0 3 0 4 3 1 5 1 5 2 3 11 8 2 3 3 6 2 0 3 0 1 1 1 3 1 0 16 8 0 0 8 13 4 0 3 0 3 0 0 0 0 0 4 7 2 0 2 8 10 0 0 0 4 0 8 2 0 0 7 1 3 5 9 1 0 2 4 0 8 0 3 2 4 1 3 0 0 1 1 5 8 1 0 0 2 4 2 0 3 0 1 3 0 2 0 1 2 15 0 5 2 13 0 3 0 0 0 1 1 3 4 1 1 2 0 4 2 2 14 1 4 5 9 0...
result:
ok 100000 tokens
Test #9:
score: 5
Accepted
time: 113ms
memory: 33240kb
input:
9 100000 1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 1 1 1 1 1 3 1 3 2 1 1 1 1 1 1 1 1 1 2 3 1 1 1...
output:
no no no no no no no no no no no yes no no no no no no no no no no no yes no no yes no no no no no no no no no no no no yes no no yes yes no no no no no no no no no no no no no yes no no no no no no no no no no no yes no no yes no no no no no no no no no no no no yes no no yes yes no no no no no no ...
result:
ok 100000 tokens
Test #10:
score: 5
Accepted
time: 99ms
memory: 33252kb
input:
10 100000 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 ...
output:
no no no no no no no no no no no no no no no yes yes no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no no no no no no no no no no yes yes no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no ...
result:
ok 100000 tokens
Test #11:
score: 0
Time Limit Exceeded
input:
11 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 ...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
12 100000 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 ...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
13 100000 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 ...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
14 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 ...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
15 100000 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
16 100000 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 ...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
17 100000 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 ...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
18 100000 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 ...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
19 100000 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 ...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
20 100000 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 ...