QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723913 | #9608. 皮鞋的多项式 | hos_lyric | 10 | 1075ms | 38728kb | C++14 | 12.1kb | 2024-11-08 03:29:43 | 2024-11-08 03:29:48 |
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")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353U;
constexpr unsigned MO2 = 2U * MO;
constexpr int FFT_MAX = 23;
using Mint = ModInt<MO>;
constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};
// as[rev(i)] <- \sum_j \zeta^(ij) as[j]
void fft(Mint *as, int n) {
assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
int m = n;
if (m >>= 1) {
for (int i = 0; i < m; ++i) {
const unsigned x = as[i + m].x; // < MO
as[i + m].x = as[i].x + MO - x; // < 2 MO
as[i].x += x; // < 2 MO
}
}
if (m >>= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned x = (prod * as[i + m]).x; // < MO
as[i + m].x = as[i].x + MO - x; // < 3 MO
as[i].x += x; // < 3 MO
}
prod *= FFT_RATIOS[__builtin_ctz(++h)];
}
}
for (; m; ) {
if (m >>= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned x = (prod * as[i + m]).x; // < MO
as[i + m].x = as[i].x + MO - x; // < 4 MO
as[i].x += x; // < 4 MO
}
prod *= FFT_RATIOS[__builtin_ctz(++h)];
}
}
if (m >>= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned x = (prod * as[i + m]).x; // < MO
as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO
as[i + m].x = as[i].x + MO - x; // < 3 MO
as[i].x += x; // < 3 MO
}
prod *= FFT_RATIOS[__builtin_ctz(++h)];
}
}
}
for (int i = 0; i < n; ++i) {
as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO
as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x; // < MO
}
}
// as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)]
void invFft(Mint *as, int n) {
assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
int m = 1;
if (m < n >> 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned long long y = as[i].x + MO - as[i + m].x; // < 2 MO
as[i].x += as[i + m].x; // < 2 MO
as[i + m].x = (prod.x * y) % MO; // < MO
}
prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
}
m <<= 1;
}
for (; m < n >> 1; m <<= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + (m >> 1); ++i) {
const unsigned long long y = as[i].x + MO2 - as[i + m].x; // < 4 MO
as[i].x += as[i + m].x; // < 4 MO
as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO
as[i + m].x = (prod.x * y) % MO; // < MO
}
for (int i = i0 + (m >> 1); i < i0 + m; ++i) {
const unsigned long long y = as[i].x + MO - as[i + m].x; // < 2 MO
as[i].x += as[i + m].x; // < 2 MO
as[i + m].x = (prod.x * y) % MO; // < MO
}
prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
}
}
if (m < n) {
for (int i = 0; i < m; ++i) {
const unsigned y = as[i].x + MO2 - as[i + m].x; // < 4 MO
as[i].x += as[i + m].x; // < 4 MO
as[i + m].x = y; // < 4 MO
}
}
const Mint invN = Mint(n).inv();
for (int i = 0; i < n; ++i) {
as[i] *= invN;
}
}
void fft(vector<Mint> &as) {
fft(as.data(), as.size());
}
void invFft(vector<Mint> &as) {
invFft(as.data(), as.size());
}
vector<Mint> convolve(vector<Mint> as, vector<Mint> bs) {
if (as.empty() || bs.empty()) return {};
const int len = as.size() + bs.size() - 1;
int n = 1;
for (; n < len; n <<= 1) {}
as.resize(n); fft(as);
bs.resize(n); fft(bs);
for (int i = 0; i < n; ++i) as[i] *= bs[i];
invFft(as);
as.resize(len);
return as;
}
vector<Mint> square(vector<Mint> as) {
if (as.empty()) return {};
const int len = as.size() + as.size() - 1;
int n = 1;
for (; n < len; n <<= 1) {}
as.resize(n); fft(as);
for (int i = 0; i < n; ++i) as[i] *= as[i];
invFft(as);
as.resize(len);
return as;
}
// m := |as|, n := |bs|
// cs[k] = \sum[i-j=k] as[i] bs[j] (0 <= k <= m-n)
// transpose of ((multiply by bs): K^[0,m-n] -> K^[0,m-1])
vector<Mint> middle(vector<Mint> as, vector<Mint> bs) {
const int m = as.size(), n = bs.size();
assert(m >= n); assert(n >= 1);
int len = 1;
for (; len < m; len <<= 1) {}
as.resize(len, 0);
fft(as);
std::reverse(bs.begin(), bs.end());
bs.resize(len, 0);
fft(bs);
for (int i = 0; i < len; ++i) as[i] *= bs[i];
invFft(as);
as.resize(m);
as.erase(as.begin(), as.begin() + (n - 1));
return as;
}
////////////////////////////////////////////////////////////////////////////////
using Poly = vector<Mint>;
// ~ (N log(N))^(1/2)
#ifdef LOCAL
constexpr int K = 2;
#else
constexpr int K = 1000;
#endif
int N, Q;
vector<Poly> C;
vector<int> A, B;
vector<vector<int>> graph;
/*
(product below u) = F[u] G[u]
deg(G[u]) < K
*/
vector<Poly *> F, G;
Poly ID{1};
Poly *mul(Poly *as, Poly *bs) {
if (as->size() == 1 && *as == ID) return bs;
if (bs->size() == 1 && *bs == ID) return as;
auto cs = new Poly;
*cs = convolve(*as, *bs);
return cs;
}
void dfs(int u, int p) {
F[u] = &ID;
G[u] = &C[u];
if ((int)G[u]->size() > K) {
swap(F[u], G[u]);
}
for (const int v : graph[u]) if (p != v) {
dfs(v, u);
F[u] = mul(F[u], F[v]);
G[u] = mul(G[u], G[v]);
if ((int)G[u]->size() > K) {
F[u] = mul(F[u], G[u]);
G[u] = &ID;
}
}
cerr<<u<<": "<<*F[u]<<" "<<*G[u]<<endl;
}
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
C.resize(N);
for (int u = 0; u < N; ++u) {
int deg;
scanf("%d", °);
C[u].resize(deg + 1);
for (int k = 0; k <= deg; ++k) {
scanf("%u", &C[u][k].x);
}
}
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
graph.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
graph[A[i]].push_back(B[i]);
graph[B[i]].push_back(A[i]);
}
F.resize(N);
G.resize(N);
dfs(0, -1);
set<Poly *> vis;
for (int u = 0; u < N; ++u) {
if (vis.insert(F[u]).second) {
for (int i = 1; i < (int)F[u]->size(); ++i) {
(*F[u])[i] += (*F[u])[i - 1];
}
}
}
int lastans = 0;
for (; Q--; ) {
int X, L, R;
scanf("%d%d%d", &X, &L, &R);
X ^= lastans;
L ^= lastans;
R ^= lastans;
// cerr<<COLOR("33")<<X<<" "<<L<<" "<<R<<COLOR()<<endl;
--X;
assert(0<=X);assert(X<N);assert(L<=R);
Mint ans = 0;
for (int i = 0; i < (int)G[X]->size(); ++i) {
int l = max(L - i, 0);
int r = min(R - i, (int)F[X]->size() - 1);
if (l <= r) {
Mint f = (*F[X])[r];
if (l) f -= (*F[X])[l - 1];
ans += f * (*G[X])[i];
}
}
printf("%u\n", ans.x);
lastans = ans.x;
}
}
return 0;
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 64ms
memory: 4756kb
input:
1977 200000 0 883734638 1 497045124 50605999 0 467033353 8 514303373 873913661 21585656 827572829 831599042 669912647 980444584 921677622 90967524 0 111009203 0 980468811 1 965285721 647475291 0 55665482 0 810210109 5 99482052 915734955 536563337 860629716 489661090 127640528 4 452261176 414532348 8...
output:
0 0 0 1462214 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 709010908 0 0 0 0 0 0 0 0 0 0 0 0 0 0 362560754 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 887205253 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 532388854 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #2:
score: 7
Accepted
time: 75ms
memory: 4824kb
input:
1969 200000 1 928278040 49291189 0 106316044 7 355985609 701602147 528629206 472008316 626845782 871506163 793475066 634852555 0 193911795 1 498772599 387035156 2 244940676 15788848 225049996 8 257966353 171785747 687353797 643745787 25069581 248781417 212047281 295151595 525248876 2 606862291 21936...
output:
0 0 702752596 0 0 0 564436252 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 539882987 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 421207407 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #3:
score: 7
Accepted
time: 104ms
memory: 4868kb
input:
2000 200000 0 230695610 4 400302240 129755410 740309716 633048240 594259574 2 261261651 610028309 279096898 0 306295327 1 411519353 880936332 4 458323735 111990362 693959473 50334178 49499787 0 451592459 1 114402580 931927324 4 639243873 254122580 669324541 571247271 275880979 0 440954066 1 43964805...
output:
0 0 801713754 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 807839363 0 845789441 0 0 0 0 0 0 0 0 180971215 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 791867965 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 514100741 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 995968989 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8782...
result:
ok 200000 numbers
Test #4:
score: 7
Accepted
time: 188ms
memory: 7448kb
input:
1978 200000 1 191987956 540466676 1 120742551 206257774 2 744430486 875250521 181042024 0 103091601 0 304724279 0 649017453 0 145685556 0 599144446 0 364188280 0 57833875 3 414338956 791946816 770890256 830048461 0 819249191 0 755199883 1 758814940 693449562 1 280052104 142092003 0 214207528 0 85521...
output:
0 0 0 0 0 0 0 0 0 0 0 0 574798441 0 0 551851346 0 0 0 0 0 0 298923018 0 0 0 0 0 706319639 0 0 932127532 0 0 0 0 506810290 0 0 375480684 0 0 0 0 0 575707276 0 769974190 0 0 0 0 0 0 0 0 0 255132253 234643792 0 436442475 0 0 0 0 0 0 770777820 0 0 0 0 382421721 0 0 10702740 0 0 912641116 0 679541132 0 0...
result:
ok 200000 numbers
Test #5:
score: 7
Accepted
time: 81ms
memory: 4856kb
input:
1997 200000 1 609381747 833571580 1 102342468 526127035 1 880931004 909374728 2 103826707 729151512 34293902 1 273372046 293953096 0 554926428 0 676458000 1 401799287 357803550 1 695810053 794616522 0 748711966 1 967175820 34877055 2 257806263 264285746 818013686 1 576641758 75701100 0 795476926 0 7...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 996352329 0 0 0 0 61024835 0 0 424430639 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 392760029 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 442026045...
result:
ok 200000 numbers
Subtask #2:
score: 3
Accepted
Test #6:
score: 3
Accepted
time: 323ms
memory: 23192kb
input:
98154 200000 0 948053956 0 149079029 0 871940052 0 888807640 0 284687863 0 760258916 0 916765457 0 121680504 0 210430381 0 162441114 0 640680402 0 269559148 0 706423649 0 619089994 0 776236890 0 44769489 0 863235377 0 283984837 0 251593760 0 863377054 0 40488948 0 100272768 0 628132233 0 18841959 0 ...
output:
0 160622568 939846745 221659137 0 312930382 620657950 975124531 0 241389446 233242086 656904774 0 666641212 127400637 0 0 61866892 388266897 17714856 158666308 181172732 0 231863345 0 0 993493871 0 945624744 0 53582097 0 553931157 940627115 0 864491900 0 0 910285591 0 0 0 0 810021023 0 957355731 870...
result:
ok 200000 numbers
Test #7:
score: 3
Accepted
time: 299ms
memory: 23056kb
input:
98566 200000 0 209181684 0 889317979 0 925862494 0 861680823 0 629292192 0 781545895 0 58892045 0 300501945 0 510137985 0 764792857 0 551445762 0 771899874 0 828696971 0 260462870 0 535761660 0 532161459 0 187099 0 691412616 0 891055462 0 283180276 0 446617517 0 928434806 0 974119517 0 895921491 0 8...
output:
0 541915644 0 0 0 344789573 37160095 0 0 378148422 0 27407348 0 510146116 0 0 593724632 308323897 0 208041958 834526238 308130263 413718362 0 0 452600858 215844992 0 0 138748183 0 597752749 0 0 0 131857104 0 0 583969453 644145934 277456647 0 730806159 210434799 329144450 0 271266199 0 0 532721033 33...
result:
ok 200000 numbers
Subtask #3:
score: 0
Time Limit Exceeded
Test #8:
score: 0
Time Limit Exceeded
input:
97330 200000 2 356080749 854511831 888131963 0 533633039 0 260190631 0 217335008 2 998111375 903316988 891866314 0 507509609 0 556810297 1 190927168 988903728 1 270553180 387224380 0 360295480 0 775464651 0 755424805 0 71030175 0 690904984 0 702271750 0 360541906 0 903384679 0 769283169 0 6990072 0 ...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #13:
score: 20
Accepted
time: 1075ms
memory: 38728kb
input:
50000 50000 1 610345459 691411093 1 476654936 529767753 1 8856530 640833948 1 961473497 456987897 1 462733802 114971681 1 662244461 415955667 1 717992437 907944693 1 346097988 176526535 1 805826501 182409272 1 33105050 971783530 1 45972429 258997374 1 964103067 796756441 1 958668755 735146502 1 9543...
output:
0 0 0 0 0 0 0 610268301 297428232 729194415 0 0 506964543 0 198345028 778136423 0 89695571 651093422 174709 799469987 0 0 0 0 374762615 64155221 0 644085102 355318236 625240586 0 0 0 0 611217681 0 246858712 0 946363040 766457000 0 0 0 0 0 0 0 885388926 324657374 0 0 608041499 0 0 0 595311003 0 0 790...
result:
ok 50000 numbers
Test #14:
score: 0
Time Limit Exceeded
input:
50000 50000 1 284188823 730123812 1 578529655 782975708 1 682107201 169640319 1 504919829 297067490 1 126340369 681480864 1 702290552 331608873 1 89823300 900339069 1 661791786 696739097 1 146107507 457302386 1 309885170 133384173 1 1601509 445278250 1 82308245 611577805 1 575317 145972663 1 3340187...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #21:
score: 20
Accepted
time: 488ms
memory: 18368kb
input:
19854 20000 1 150513542 240180212 0 987796281 0 90054116 1 191708494 438440429 0 192815969 0 867402303 1 531762469 210966860 2 95662022 345368425 199338548 0 269135053 0 816253511 0 66854944 0 319745952 0 202288549 0 492853777 0 410846691 0 824737426 0 821545014 0 72050044 0 534080091 1 542636124 52...
output:
913323334 0 0 0 0 0 0 0 0 0 0 0 901017606 0 0 0 0 0 954099396 0 0 432419999 0 0 0 0 0 0 0 761082946 259729654 0 0 0 0 790235355 933098570 356668385 125624181 0 0 0 0 917034405 0 321407524 0 671256345 39032345 0 0 676929142 0 0 0 0 0 0 0 0 910494481 0 0 0 733125978 0 0 835461650 0 154343024 690428959...
result:
ok 20000 numbers
Test #22:
score: 20
Accepted
time: 424ms
memory: 15988kb
input:
19416 20000 1 813812350 62928444 2 446931520 455152410 865811291 1 483245225 719509880 0 10630578 1 722267364 499990463 0 978295677 0 524126644 2 398577038 701788899 939255653 0 945953310 0 358029034 1 54632159 541649711 0 714215963 0 760637762 1 792667329 540131052 1 336329275 197811762 0 594815129...
output:
0 0 0 0 0 0 0 0 691960524 0 0 0 0 0 0 0 0 0 0 917519575 0 0 0 0 457906160 686627668 0 263875204 0 0 0 860458574 0 0 197732443 0 0 0 0 0 0 0 0 0 0 0 0 0 619069496 0 0 145464796 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 409777622 309523189 862407937 0 0 954411456 0 0 0 0 0 0 304719397 0 548777971 176155...
result:
ok 20000 numbers
Test #23:
score: 20
Accepted
time: 400ms
memory: 16288kb
input:
19645 20000 1 738216072 655062389 0 478261419 28 38522218 205802590 608351714 423733656 368037127 943951223 529243126 691493532 378826276 32699256 849862664 799709335 113704178 671006657 736000878 683394539 338518052 850384023 536423162 225738416 276528868 965415989 455460104 274736758 547583027 423...
output:
0 710035374 349663621 61124181 0 0 0 0 0 0 0 0 0 0 0 0 0 0 694466943 0 0 0 0 103025366 0 0 108158012 0 0 898653012 0 0 0 0 124734988 0 628306562 0 0 0 0 0 829055370 0 942321667 0 0 0 0 100614270 0 666765805 277413825 0 0 0 0 492192785 0 0 0 0 517011159 0 0 0 0 172598073 0 258513717 233404540 8590182...
result:
ok 20000 numbers
Test #24:
score: 20
Accepted
time: 400ms
memory: 15516kb
input:
19847 20000 4 815026590 930615671 256423615 192058090 553677398 0 854407447 3 121205405 14847480 141687199 287623506 2 379798536 291209656 593839232 1 352031200 841240984 0 295186159 0 841042115 0 679392127 0 420742492 2 891756622 260075296 417909411 0 645458804 0 681889229 0 29119165 0 99142741 3 7...
output:
470171472 213398321 0 0 55462715 0 338144412 0 0 0 0 0 0 0 698725184 0 0 0 0 47366191 0 317326831 0 0 0 239746199 214366720 0 0 0 0 0 279091720 0 86836316 0 0 0 35432299 0 308555884 0 319326811 0 0 0 305535605 0 358646410 0 0 131375996 0 0 0 0 0 0 0 0 570823027 0 0 80022023 0 954809219 0 0 0 0 26917...
result:
ok 20000 numbers
Test #25:
score: 20
Accepted
time: 380ms
memory: 16240kb
input:
19990 20000 3 575964327 889968526 762346953 464212918 0 91433877 0 762285092 1 703259059 61874142 2 130773960 696187633 280576635 1 163442506 294293968 0 134582456 0 525908094 2 981613234 494831823 871173319 0 320232487 0 951459253 0 725136632 2 48590419 631199232 992008959 1 860836891 867326137 1 6...
output:
90336621 0 741001438 326700634 0 0 0 0 0 0 925215064 0 0 863889195 0 0 0 0 0 576304546 0 0 0 0 583889751 0 0 0 0 0 0 813389361 0 0 0 0 0 0 0 108311310 0 0 653689603 0 0 0 91295650 0 347062400 0 0 0 0 620038417 846141331 99345412 0 581988923 0 0 0 0 365053652 29464872 917029396 788177507 288943414 0 ...
result:
ok 20000 numbers
Test #26:
score: 20
Accepted
time: 448ms
memory: 16200kb
input:
19302 20000 1 140879209 815790450 0 263312184 2 357492390 407721624 927753023 17 329030216 687250506 904721674 66559073 150996400 582272412 140464848 806623151 989399143 916248414 596527559 964780629 802988469 182625819 764316767 594475067 203564894 275476377 0 547777698 0 34169169 0 93303556 0 5807...
output:
0 0 132910965 0 127962650 0 453633700 0 0 451482843 0 0 0 388743057 0 0 293560154 874329518 0 0 0 0 0 0 0 0 0 0 766081674 0 0 234642116 0 0 669563153 0 748448386 0 0 0 0 0 0 0 0 0 670410122 87350607 0 416323263 174794844 0 0 0 0 0 0 196859095 0 0 0 0 644332981 0 0 0 0 0 0 0 0 0 469599960 0 0 0 0 931...
result:
ok 20000 numbers
Test #27:
score: 20
Accepted
time: 456ms
memory: 18764kb
input:
19653 20000 1 906614788 500628713 0 988012762 0 284902421 0 704468047 0 872560811 1 907887753 600402772 0 767950811 0 118754288 0 290736011 0 217729487 1 190172852 683598286 0 723859834 0 220112811 0 448174595 0 39653265 0 770732977 0 458450918 0 438730398 0 183195813 0 191514564 0 2928127 0 3007322...
output:
0 244727120 0 0 132988676 354295625 0 667761790 0 0 0 0 0 822615931 0 0 0 0 0 0 504618092 0 973780962 0 0 0 0 737475269 0 0 0 383245743 0 0 10261578 551768502 0 835642191 0 0 69015099 0 0 773914454 0 0 0 0 0 193232063 0 0 0 0 0 230203189 0 0 0 0 0 0 0 0 120778708 0 949822563 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 20000 numbers
Test #28:
score: 20
Accepted
time: 332ms
memory: 15592kb
input:
19072 20000 0 910136763 1 809343877 577693489 0 805540439 0 728993500 0 234081004 1 891104112 210354669 0 262384318 0 568913493 0 376708574 1 145377149 421745582 0 108964429 0 697119989 0 615671424 0 697025092 0 222804661 0 927317484 1 66775292 771115618 0 405877157 1 977355316 502648356 1 218406564...
output:
0 0 0 558272462 0 0 0 0 0 0 0 328733917 446478844 0 0 0 0 0 0 848724549 0 0 980511070 0 0 597411269 0 127279175 0 0 0 0 0 739852501 0 0 0 0 0 0 568449517 589452941 0 0 0 0 791777304 0 0 0 0 114744131 322763812 613885875 52417149 0 0 0 0 149449664 0 0 644257795 0 725958460 276312482 499158209 8075964...
result:
ok 20000 numbers
Test #29:
score: 0
Time Limit Exceeded
input:
20000 20000 0 614936162 0 182986322 0 40697275 0 824161988 0 240412566 0 287310162 0 63000758 0 958628891 0 139827408 0 971860786 0 325782161 0 726800064 0 392930207 0 911604309 0 904980384 0 508941069 0 641836609 0 759719860 0 732767740 0 94630498 0 390558752 0 764408563 0 40013248 0 414628626 0 87...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%