QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #349829 | #8335. Fast Hash Transform | ucup-team2894# | AC ✓ | 1671ms | 47160kb | C++20 | 20.4kb | 2024-03-10 06:11:18 | 2024-03-10 06:11:18 |
Judging History
answer
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())
#define popcnt(x) __builtin_popcountll(x)
using namespace std;
#ifdef ONPC
mt19937 rnd(223);
mt19937 rndll(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
.time_since_epoch().count());
mt19937 rndll(223);
#endif
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ld = double;
const int maxn = 2e4 + 100, inf = 1e9 + 100;
#define uint oleg
using uint = uint64_t;
using Mat = array<uint, 64>;
const uint one = 1;
inline bool mult(uint x, uint y) {
return popcnt(x & y) & 1;
}
struct Li {
Mat a{};
uint b{};
void upd(int i, int j, bool w) {
if (w)
a[j] ^= (one << i);
}
uint apply(uint x) const {
uint w = 0;
for (int i = 0; i < 64; i++)
if (mult(x, a[i]))
w ^= (one << i);
return w ^ b;
}
};
Li def() {
Li q{};
for (int i = 0; i < 64; i++)
q.upd(i, i, 1);
return q;
}
Mat c{};
Li comb(Li const &x, Li const &y) {
c = {};
Li q{};
for (int i = 0; i < 64; i++)
for (int j = 0; j < 64; j++)
if (x.a[j] & (one << i))
c[i] ^= (one << j);
for (int i = 0; i < 64; i++)
for (int j = 0; j < 64; j++)
q.upd(i, j, mult(c[i], y.a[j]));
q.b = y.apply(x.b);
return q;
}
namespace segtree {
// This implementation is disgusting, but it seems to work and do it faster than previous version.
template<typename Item>
Item tree_merge(const Item& a, const Item& b) {
Item i;
i.update(a, b);
return i;
}
template<typename Item, bool lazy>
struct Pusher {};
template<typename Item>
struct Pusher<Item, false> {
void push(const vector<Item>&, int, int, int) {}
uint ask_on_segment(const vector<Item>& tree, int n, int l, int r, uint w) {
l |= n;
r |= n;
Item resl, resr;
static vector<int> pos;
pos.clear();
while (l <= r) {
if (l & 1) {
w = tree[l].w.apply(w);
// resl = tree_merge(resl, tree[l]);
++l;
}
if (!(r & 1)) {
pos.push_back(r);
// resr = tree_merge(tree[r], resr);
--r;
}
l >>= 1;
r >>= 1;
}
reverse(all(pos));
for (int i : pos)
w = tree[i].w.apply(w);
return w;
}
void push_point(const vector<Item>&, int, int) {}
template<typename P>
int lower_bound(const vector<Item>& tree, int n, int l, P p) {
Item cur;
if (p(cur)) return l - 1;
l |= n;
int r = n | (n - 1);
// carefully go up
while (true) {
if (p(tree_merge(cur, tree[l]))) {
break;
}
if (l == r) return n;
if (l & 1) {
cur = tree_merge(cur, tree[l]);
++l;
}
l >>= 1;
r >>= 1;
}
// usual descent from l
while (l < n) {
if (p(tree_merge(cur, tree[l * 2]))) {
l = l * 2;
} else {
cur = tree_merge(cur, tree[l * 2]);
l = l * 2 + 1;
}
}
return (l ^ n);
}
template<typename P>
int lower_bound_rev(const vector<Item>& tree, int n, int r, P p) {
Item cur;
if (p(cur)) return r + 1;
r |= n;
int l = n;
// carefully go up
while (true) {
if (p(tree_merge(tree[r], cur))) {
break;
}
if (l == r) return -1;
if (!(r & 1)) {
cur = tree_merge(tree[r], cur);
--r;
}
l >>= 1;
r >>= 1;
}
// usual descent from r
while (r < n) {
if (p(tree_merge(tree[r * 2 + 1], cur))) {
r = r * 2 + 1;
} else {
cur = tree_merge(tree[r * 2 + 1], cur);
r = r * 2;
}
}
return (r ^ n);
}
};
template<typename Item>
struct Pusher<Item, true> {
void push(vector<Item>& tree, int ind, int l, int r) {
tree[ind].push(tree[ind * 2], tree[ind * 2 + 1], l, r);
}
Item ask_on_segment(vector<Item>& tree, int n, int l, int r) {
int vl = 0, vr = n - 1;
int i = 1;
Item result;
while (vl != vr) {
int m = (vl + vr) / 2;
if (l > m) {
push(tree, i, vl, vr);
i = i * 2 + 1;
vl = m + 1;
} else if (r <= m) {
push(tree, i, vl, vr);
i = i * 2;
vr = m;
} else {
break;
}
}
if (l == vl && r == vr) {
return tree[i];
}
push(tree, i, vl, vr);
// left
{
int ind = i * 2;
int L = vl, R = (vl + vr) / 2;
while (l != L) {
int m = (L + R) / 2;
push(tree, ind, L, R);
if (l <= m) {
result = tree_merge(tree[ind * 2 + 1], result);
ind *= 2;
R = m;
} else {
ind = ind * 2 + 1;
L = m + 1;
}
}
result = tree_merge(tree[ind], result);
}
// right
{
int ind = i * 2 + 1;
int L = (vl + vr) / 2 + 1, R = vr;
while (r != R) {
int m = (L + R) / 2;
push(tree, ind, L, R);
if (r > m) {
result = tree_merge(result, tree[ind * 2]);
ind = ind * 2 + 1;
L = m + 1;
} else {
ind = ind * 2;
R = m;
}
}
result = tree_merge(result, tree[ind]);
}
return result;
}
void push_point(vector<Item>& tree, int n, int ind) {
int l = 0, r = n - 1;
int i = 1;
while (l != r) {
push(tree, i, l, r);
int m = (l + r) / 2;
if (ind <= m) {
r = m;
i *= 2;
} else {
l = m + 1;
i = i * 2 + 1;
}
}
}
template<typename P>
pair<int, Item> _lower_bound(vector<Item>& tree, int l, P p, Item cur, int i, int vl, int vr) {
if (vl == vr) {
if (p(tree_merge(cur, tree[i]))) {
return {vl, tree[i]};
} else {
return {vl + 1, tree[i]};
}
}
push(tree, i, vl, vr);
int m = (vl + vr) / 2;
if (l > m) {
return _lower_bound(tree, l, p, cur, i * 2 + 1, m + 1, vr);
} else if (l <= vl) {
if (!p(tree_merge(cur, tree[i]))) {
return {vr + 1, tree_merge(cur, tree[i])};
}
if (p(tree_merge(cur, tree[i * 2]))) {
return _lower_bound(tree, l, p, cur, i * 2, vl, m);
} else {
return _lower_bound(tree, l, p, tree_merge(cur, tree[i * 2]), i * 2 + 1, m + 1, vr);
}
} else {
auto [ind, it] = _lower_bound(tree, l, p, cur, i * 2, vl, m);
if (ind <= m) return {ind, it};
return _lower_bound(tree, l, p, it, i * 2 + 1, m + 1, vr);
}
}
template<typename P>
int lower_bound(vector<Item>& tree, int n, int l, P p) {
Item cur;
if (p(cur)) return l - 1;
return _lower_bound(tree, l, p, cur, 1, 0, n - 1).first;
}
template<typename P>
pair<int, Item> _lower_bound_rev(vector<Item>& tree, int r, P p, Item cur, int i, int vl, int vr) {
if (vl == vr) {
if (p(tree_merge(tree[i], cur))) {
return {vl, tree[i]};
} else {
return {vl - 1, tree[i]};
}
}
push(tree, i, vl, vr);
int m = (vl + vr) / 2;
if (r <= m) {
return _lower_bound_rev(tree, r, p, cur, i * 2, vl, m);
} else if (r >= vr) {
if (!p(tree_merge(tree[i], cur))) {
return {vl - 1, tree_merge(cur, tree[i])};
}
if (p(tree_merge(tree[i * 2 + 1], cur))) {
return _lower_bound_rev(tree, r, p, cur, i * 2 + 1, m + 1, vr);
} else {
return _lower_bound_rev(tree, r, p, tree_merge(tree[i * 2 + 1], cur), i * 2, vl, m);
}
} else {
auto [ind, it] = _lower_bound_rev(tree, r, p, cur, i * 2 + 1, m + 1, vr);
if (ind > m) return {ind, it};
return _lower_bound_rev(tree, r, p, it, i * 2, vl, m);
}
}
template<typename P>
int lower_bound_rev(vector<Item>& tree, int n, int r, P p) {
Item cur;
if (p(cur)) return r + 1;
return _lower_bound_rev(tree, r, p, cur, 1, 0, n - 1).first;
}
};
template<typename Item, bool lazy = false>
struct Segtree {
vector<Item> tree;
Pusher<Item, lazy> pusher;
int n;
int n0;
Segtree(int n = 0) {
build(n);
}
template<typename U>
Segtree(const vector<U>& v) {
build(v);
}
void build(int n) {
this->n0 = n;
while (n & (n - 1)) ++n;
this->n = n;
tree.assign(n * 2, {});
}
template<typename U>
void build(const vector<U>& v) {
build(v.size());
for (int i = 0; i < v.size(); ++i) {
tree[n | i].init(v[i], i);
}
build();
}
void build() {
for (int i = n - 1; i >= 1; --i) {
tree[i].update(tree[i * 2], tree[i * 2 + 1]);
}
}
void push(int ind, int l, int r) {
pusher.push(tree, ind, l, r);
}
template<typename T>
void set(int ind, const T& t) {
pusher.push_point(tree, n, ind);
ind |= n;
tree[ind].init(t, ind ^ n);
ind >>= 1;
while (ind) {
tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
ind >>= 1;
}
}
template<typename T>
void update(int ind, const T& t) {
pusher.push_point(tree, n, ind);
ind |= n;
tree[ind].update(t, ind ^ n);
ind >>= 1;
while (ind) {
tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
ind >>= 1;
}
}
Item& ith(int ind) {
static_assert(!lazy, "don't use this method with lazy propagation, unless you're sure you need it");
return tree[ind | n];
}
const Item& root() const {
return tree[1];
}
uint ask(int l, int r, uint w) {
l = max(l, 0);
r = min(r, n - 1);
if (l > r) return 0;
return pusher.ask_on_segment(tree, n, l, r, w);
}
template<typename T>
void modify(int l, int r, const T& t) {
static_assert(lazy, "lazy must be set to true to use this function");
l = max(l, 0);
r = min(r, n - 1);
if (l > r) return;
int vl = 0, vr = n - 1;
int i = 1;
while (vl != vr) {
int m = (vl + vr) / 2;
if (l > m) {
push(i, vl, vr);
i = i * 2 + 1;
vl = m + 1;
} else if (r <= m) {
push(i, vl, vr);
i = i * 2;
vr = m;
} else {
break;
}
}
if (l == vl && r == vr) {
tree[i].modify(t, l, r);
} else {
push(i, vl, vr);
// left
{
int ind = i * 2;
int L = vl, R = (vl + vr) / 2;
while (l != L) {
int m = (L + R) / 2;
push(ind, L, R);
if (l <= m) {
tree[ind * 2 + 1].modify(t, m + 1, R);
ind *= 2;
R = m;
} else {
ind = ind * 2 + 1;
L = m + 1;
}
}
tree[ind].modify(t, L, R);
ind >>= 1;
while (ind != i) {
tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
ind >>= 1;
}
}
// right
{
int ind = i * 2 + 1;
int L = (vl + vr) / 2 + 1, R = vr;
while (r != R) {
int m = (L + R) / 2;
push(ind, L, R);
if (r > m) {
tree[ind * 2].modify(t, L, m);
ind = ind * 2 + 1;
L = m + 1;
} else {
ind = ind * 2;
R = m;
}
}
tree[ind].modify(t, L, R);
ind >>= 1;
while (ind != i) {
tree[ind].update(tree[ind * 2], tree[ind * 2 + 1]);
ind >>= 1;
}
}
tree[i].update(tree[i * 2], tree[i * 2 + 1]);
}
i >>= 1;
while (i) {
tree[i].update(tree[i * 2], tree[i * 2 + 1]);
i >>= 1;
}
}
// first index r such that p(tree.ask(l, r)) == true
// if p() is true for empty item, return l-1
// if p() is never true, returns n
template<typename P>
int lower_bound(int l, P p) {
l = max(l, 0);
if (l >= n0) return n0;
return min(n0, pusher.lower_bound(tree, n, l, p));
}
// similarly to lower_bound, returns first (largest) l such that p(tree.ask(l, r)) == true
template<typename P>
int lower_bound_rev(int r, P p) {
r = min(r, n0 - 1);
if (r < 0) return -1;
return pusher.lower_bound_rev(tree, n, r, p);
}
};
}
using segtree::Segtree;
#define cin if(1)cin
Li read_hash() {
int m = 64;
cin >> m;
Li q;
for (int it = 0; it < m; it++) {
int s = it, o = rnd() & 1;
uint A = rndll();
cin >> s >> o >> A;
if (o == 0) {
// or
for (int i = 0; i < 64; i++)
if (A & (one << i)) {
q.b ^= (one << i);
}
A = ~A;
}
{
// and
for (int i = 0; i < 64; i++) {
int pe = (i + s) % 64;
q.upd(i, pe, (A >> pe) & 1);
}
}
}
uint b;
cin >> b;
q.b ^= b;
// for (int j = 0; j < 64; j++)
// cerr << q.a[j] << '\n';
// cerr << q.b << '\n';
// cerr << "-----------------\n";
return q;
}
struct Item {
Li w = def();
template<typename T>
void init(const T& t, int ind) {
w = t;
}
void update(const Item& a, const Item& b) {
w = comb(a.w, b.w);
}
//// similar to init, but more convenient for doing a[i] += x, implement only if needed
// template<typename T>
// void update(const T& t, int ind) {}
//// apply here, save for children
// template<typename T>
// void modify(const T& m, int l, int r) {}
// void push(Item& a, Item& b, int l, int r) {
// int m = (l + r) / 2;
// a.modify(mod, l, m);
// b.modify(mod, m + 1, r);
// // reset mod
// }
};
//const int LG = 16;
//Li q[LG][maxn];
vector<Li> a;
//
//void build(int h, int l, int r) {
// if (l == r) {
// return;
// }
// int m = (l + r) / 2;
// Li z = def();
// for (int i = m; i >= l; i--) {
// z = comb(a[i], z);
// q[h][i] = z;
// }
// z = def();
// for (int i = m + 1; i <= r; i++) {
// z = comb(z, a[i]);
// q[h][i] = z;
// }
// build(h + 1, l, m);
// build(h + 1, m + 1, r);
//}
//
//Li get(int h, int tl, int tr, int l, int r) {
// int m = (tl + tr) / 2;
// if (l <= m && r > m) {
// return comb(q[h][l], q[h][r]);
// }
// if (r <= m) {
// return get(h + 1, tl, m, l, r);
// }
// return get(h + 1, m + 1, tr, l, r);
//}
//
//void update(int h, int l, int r, int i) {
// if (l == r)
// return;
// int m = (l + r) / 2;
// if (i <= m) {
// Li z = def();
// for (int i = m; i >= l; i--) {
// z = comb(a[i], z);
// q[h][i] = z;
// }
// update(h + 1, l, m, i);
// } else {
// Li z = def();
// for (int i = m + 1; i <= r; i++) {
// z = comb(z, a[i]);
// q[h][i] = z;
// }
// update(h + 1, m + 1, r, i);
// }
//}
void solve() {
int n, zaps, C;
n = zaps = 20000;
C = 1;
cin >> n >> zaps >> C;
a.resize(n);
for (int i = 0; i < n; i++) {
a[i] = read_hash();
}
cerr << "\n\nreading " << TIME << endl;
Segtree<Item> t(a);
//build(0, 0, n - 1);
cerr << "\n\nbuilding " << TIME << endl;
while (zaps--) {
int tp;
tp = rnd() & 1;
tp = 0;
cin >> tp;
if (tp == 0) {
int l, r;
l = rnd() % n + 1;
r = rnd() % n + 1;
if (l > r)
swap(l, r);
uint x = rndll();
cin >> l >> r >> x;
l--;
r--;
if (l == r)
cout << a[l].apply(x) << '\n';
else {
// cout << get(0, 0, n - 1, l, r).apply(x) << '\n';
// Li z = def();
// for (int i = l; i <= r; i++)
// z = comb(z, a[i]);
cout << t.ask(l, r, x) << '\n';
}
} else {
int i;
i = rnd() % n + 1;
cin >> i;
i--;
a[i] = read_hash();
// update(0, 0, n - 1, i);
t.set(i, a[i]);
}
}
}
int main() {
#ifdef ONPC
freopen("../a.in", "r", stdin);
freopen("../a.out", "w", stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(20);
solve();
cerr << "\n\nConsumed " << TIME << endl;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
3 5 1 1 4 0 0 51966 1 60 0 0 0 1 0 0 16 15 0 1 1 771 0 2 2 32368 0 3 3 0 1 2 2 0 0 15 61 1 4095 46681 0 1 3 2023
output:
64206 2023 31 1112
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
9 9 3 32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...
output:
9487331362121050549 3906661590723083106 15757672015979182109 4975471776251039345 11503109206538591140 3763610618439604410
result:
ok 6 tokens
Test #3:
score: 0
Accepted
time: 19ms
memory: 3932kb
input:
1 20000 400 32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...
output:
11827781865759498816 7454610526276185721 9581050724293785387 2177163806257271094 14004004964877510141 18073834598135159471 16966489063087641088 12289032565388413023 17823140805867698239 18104549908461644670 15570008264282957124 12400954982104000299 9842549278742638708 16535034933613060362 1561642006...
result:
ok 19600 tokens
Test #4:
score: 0
Accepted
time: 195ms
memory: 4376kb
input:
500 20000 400 32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...
output:
9119093329811149961 16901643057538871933 17161855998497876349 3964234071281411558 13588188063229334268 15557968976322375381 4612345875926431452 9507168112801039022 9504318642653891468 217407202160767706 12982350345598971306 17957502630817476223 6353877977318728572 15552768639781831485 16778108770682...
result:
ok 19600 tokens
Test #5:
score: 0
Accepted
time: 428ms
memory: 9692kb
input:
4000 20000 400 35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...
output:
11875257514484243925 3443357416933857062 16160011677622853538 1582145987019406393 15019762274690743371 3128972641411454448 10632018957963074870 2420532366876270818 16130728863118353230 15834956073901517645 18404809296474853851 10982435108266120760 16463778300806795274 11990886156320593058 1145171640...
result:
ok 19600 tokens
Test #6:
score: 0
Accepted
time: 1095ms
memory: 47032kb
input:
20000 20000 0 34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...
output:
8031710763259664674 10015579400510819759 9509776159199873854 252965904282343862 17471441301398284397 6167329408972068582 11581702001320217920 13373488743211628824 2094753313448112669 15503010008451014749 384500896248723935 10501371892025480221 8907735695899875922 14479597201387282763 164403466075406...
result:
ok 20000 tokens
Test #7:
score: 0
Accepted
time: 1095ms
memory: 47060kb
input:
20000 20000 20 28 31 1 17220760822712602145 12 1 10079395927654210001 40 0 10440736241216457314 20 1 14759495678166748212 55 1 8734257463550073646 60 0 543206106562221008 29 1 5402811237936853387 52 1 3884345269948184760 22 0 7873959847686200341 15 1 18396630536251250330 25 0 18230407003294263406 14...
output:
6531775129959975384 6212576544894999781 4191848452578359691 2769536540387251859 15526337103142577854 14948743844803225542 15235110724610778185 9004056994453026335 1028305510694260706 13496210650896843548 13961471020487846633 1864980030930734934 15243868808579626755 10451839696548403150 1178402342726...
result:
ok 19980 tokens
Test #8:
score: 0
Accepted
time: 1307ms
memory: 47004kb
input:
20000 20000 400 41 15 1 10590708978689078436 33 0 17448869030270552656 37 1 16782453056389226553 2 1 18313039076194285622 53 1 7894371271572806769 60 1 14563226108042670650 56 0 12694119759311053234 12 1 969626878679760122 28 1 8906626075909573228 20 1 11632670066953088447 50 0 13097960756795495550 ...
output:
7425391644666486729 17533666397961516801 16986235811843827275 1784742314571007240 13192305384063626572 12739810377012216000 1179361465141596122 7698346401428161235 6903188112913915716 5380404381348976227 16126105607866972637 12798978320947566556 11234201442491665890 16073897288956866956 151328474491...
result:
ok 19600 tokens
Test #9:
score: 0
Accepted
time: 1310ms
memory: 46996kb
input:
20000 20000 400 33 39 1 17067623245236507261 27 1 7041428814521205530 50 1 10823426118594256003 28 1 7163716190894912799 12 1 4080987667516350158 63 0 17082717673883070565 17 0 11310350135715835231 51 1 12855244004029414317 38 0 9814237273168847221 57 1 3708701962235763971 37 0 10158992933772396697 ...
output:
6864973236048047224 18318008901523164537 13500746067907696382 13161681605750995854 3452654261090196316 14847903013724109682 7301818645657195470 15784097910646013208 6555334273152043996 6337001136120562705 7065460407919669838 17502323856909932125 12099828260978288865 17244785354672463736 159661862214...
result:
ok 19600 tokens
Test #10:
score: 0
Accepted
time: 1037ms
memory: 47056kb
input:
20000 20000 0 37 46 0 4806156443854081866 29 0 6910842714881233745 61 0 9379366064412681113 32 1 718568893402460472 45 0 1234243654449881049 16 0 9791590151480029686 24 1 801156398497308107 20 1 1638149966892153162 3 1 483739892768149714 56 1 3070030763953269690 38 1 11944075913457601606 6 1 8068547...
output:
17693343388614420171 11014279187501816246 7111154205373939902 5948421254644613369 5776121468606637836 16944170640450069348 8394185836099893155 11947149219582604015 4508739183749291929 11471060687727420580 3924131475517252887 1743542114579130111 14487529569441993654 8062193838630657668 18359613799309...
result:
ok 20000 tokens
Test #11:
score: 0
Accepted
time: 1248ms
memory: 47024kb
input:
20000 20000 400 31 63 1 14360706182574306953 17 0 4643864577315796645 48 0 11264878137122897405 18 1 14150130986659920202 25 1 15979000250901513596 49 0 16241841209566112679 37 1 16762565151400121253 14 1 7376170230332808198 26 1 10868082441744868454 27 1 6949308347230687639 44 1 4116452321258930556...
output:
4493451016206578040 14208826853413050113 15020158700931574670 16337826900074673926 5403566933376608394 8871156492968482557 8911109963819675601 6213157285507240354 17190717170193641517 15578273901773478953 1369444627312020075 11786462107951385516 17634527799358234224 18347358352139830828 145863906383...
result:
ok 19600 tokens
Test #12:
score: 0
Accepted
time: 1117ms
memory: 47032kb
input:
20000 20000 0 25 16 0 2668205375195949736 34 0 2748287585311204102 37 1 4531486636255948251 24 0 14410309392802368907 52 1 851885811168352867 47 1 15887239727531457455 42 0 8819527325570258215 44 0 16146066124743535517 46 1 1041563265194349313 11 1 13140073107604291185 0 1 16670532562293262804 56 1 ...
output:
5924012028700061898 4718073419648080016 13993322115865028469 82790239609178342 887419913876033685 15321668567642867070 8962935781265467660 1552533755174937777 16683793257623944188 6900756788022393102 10981237528745871227 5789630421744738481 9056874037200094100 15328577526113324947 627381852022728881...
result:
ok 20000 tokens
Test #13:
score: 0
Accepted
time: 1330ms
memory: 47160kb
input:
20000 20000 400 29 26 0 4544814232153615705 62 0 13471881549916225637 53 0 595040484360290534 17 1 11949377632182068615 20 0 9311349995021422035 60 0 816595034603135343 48 0 10654197142859256352 24 0 4772788762907504538 54 0 15584542718632709463 19 1 2151387765439259665 41 1 15099291996319444694 40 ...
output:
1423325416659742802 17371677980372930727 3681232738426467215 13266462173687709877 12639633063779823269 1946619485256865431 12989302207328517036 14138867084917472527 18218337902938347758 3372796243270362661 673871038008779791 9077527952253879051 7326631285358366273 2710349874806590369 172928358344422...
result:
ok 19600 tokens
Test #14:
score: 0
Accepted
time: 1332ms
memory: 46964kb
input:
20000 20000 400 24 38 1 3460586314685566112 26 0 4188084273268315686 61 0 1227557406397452582 25 1 5747999803901747386 41 1 1907261769878407698 27 0 16752772615002344376 34 0 17112817990633067537 60 0 9291256903378353577 45 0 7510343555807629464 13 0 18007693761515887577 9 1 17317953029923040761 4 0...
output:
13100999329968562920 15516017614708332089 5382331705592343945 357522576585990254 16311520569626827168 6758986479859611544 12732461424037837989 8966988217248420501 10391550114259677068 4660694210255306341 7237506373169380284 13657244350225493605 6916780657676036471 10881113620462446827 16277857127600...
result:
ok 19600 tokens
Test #15:
score: 0
Accepted
time: 1650ms
memory: 46976kb
input:
20000 20000 400 60 25 1 2719522369398288789 40 1 9400902170286318935 6 1 9521944178235051324 43 0 11768204916287391421 22 0 12726538799306592512 47 1 15759776307217345226 17 1 15438840904724459733 13 0 17863856648581711698 29 1 4032777103500438360 10 0 683992519125165540 26 1 15461667428831774672 14...
output:
412280358023687627 14769812881817125733 18318455003071307239 6658808483284331159 6130439376668456888 1492308137069243960 5853920885317257980 12553163529022332915 7520793755811132601 13993258994649409340 13568418050081351467 12309096149487021368 17899306611786296579 2598853739059100346 14630776750608...
result:
ok 19600 tokens
Test #16:
score: 0
Accepted
time: 1656ms
memory: 47024kb
input:
20000 20000 400 58 17 0 7751036624596546188 29 0 17432650278695392920 63 0 4389503693497138241 24 0 11063030485327807810 45 1 18240337466752243882 59 1 17804018980843534887 60 1 5872699360277748939 21 1 10429471649278268372 27 0 16762274761588446397 54 0 6030940442592696599 19 1 13270942932118095691...
output:
17867517807501868664 7775943633465469655 1824462793515136478 12630456144448858727 16944355600951673184 14837233611662521712 13878709289450326681 13750017221938869139 11379793111096427897 15527971528797740116 5872004578520784281 11280146030218952435 5218412287620909707 15541801824852151484 5650476389...
result:
ok 19600 tokens
Test #17:
score: 0
Accepted
time: 1648ms
memory: 47036kb
input:
20000 20000 400 60 22 0 12707603241789460389 46 0 15086313545825117890 33 0 909121147706895901 59 1 6114670732197551336 41 0 3090389396605293219 63 0 6608018621123394175 38 1 11836608073091750746 14 1 4878457553941336535 5 0 6024711164477768229 25 1 67199414342206654 24 0 1139176812912408779 16 0 12...
output:
11101670153251608253 675780991220106254 15866623643054791619 16323951405331282505 9135544362908319645 7642151295897109981 12351493946367393308 1935066719605622920 7518368202469961257 11600515247827283279 15933103715396571729 13453007077105135208 14727385649041622999 123215011875209372 76221879547507...
result:
ok 19600 tokens
Test #18:
score: 0
Accepted
time: 1666ms
memory: 47076kb
input:
20000 20000 400 57 0 1 16995927798044259033 30 1 4411529108320693455 35 1 14740826024996968953 32 1 14741500464787789772 5 1 13621297821910096766 47 1 1805557230674866983 26 0 1852515218899978614 37 1 14167448543730803554 15 0 8207408801869448845 7 0 2253659179521891807 61 1 1303777112793499927 1 1 ...
output:
14640221015002441272 8108797686286238378 619977752116985977 17860455208859938460 2219391733727955287 17098130710123326231 4643402762732727695 1576822124091279449 2112594951252396904 11012866398108256228 3100264803360198048 1520325785935749501 17234063909328734373 2294517371241459639 6577965043160831...
result:
ok 19600 tokens
Test #19:
score: 0
Accepted
time: 1661ms
memory: 46972kb
input:
20000 20000 400 60 23 1 12967402093469929995 29 0 12482782180176810891 47 1 17290909632526370536 5 0 17372530581982291607 62 1 13987764289696466564 41 1 8421162609706963610 53 0 18089202028338115523 10 0 1312033850971950221 2 0 3337291528457528731 18 1 17751876270582349954 32 0 13359684730271699557 ...
output:
8219634040467306280 7488593258162917054 3429645423088159837 13823280993584110417 4972072459402131521 8504404100763034378 5815021261728531941 5670841473953742448 6721982245071008063 8353993923949852878 4277531481899017404 5173775653727609205 4061296038432070306 11044359884601198871 272114767395246212...
result:
ok 19600 tokens
Test #20:
score: 0
Accepted
time: 1671ms
memory: 47024kb
input:
20000 20000 400 56 3 0 14386867255986651070 17 1 5876678743420202175 24 0 2472800002233203764 40 0 3974575279492546522 5 1 10323896862538344788 31 0 15302550669828857297 10 0 8188514003112427229 28 0 9350793473465284653 34 1 1051624389221640716 56 1 12992224832956122800 0 1 12521917684359350214 33 1...
output:
16023098103166573969 5488057777512126106 2364974952009032490 6867156023979603961 13898097818261510588 3896697852262723116 13075557814956081246 550932186457628322 1501306951093128873 12801415593941350129 12431218450278358855 8287212554931924015 7521994383511852994 7781645210267880075 1658905057583045...
result:
ok 19600 tokens
Extra Test:
score: 0
Extra Test Passed