QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#251894#7775. 【模板】矩阵快速幂hos_lyric#40 657ms4260kbC++148.9kb2023-11-15 12:13:202024-07-04 02:25:22

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:25:22]
  • 评测
  • 测评结果:40
  • 用时:657ms
  • 内存:4260kb
  • [2023-11-15 12:13:20]
  • 提交

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")


#ifndef LIBRA_OTHER_INT128_H_
#define LIBRA_OTHER_INT128_H_

#include <stdio.h>
#include <iostream>

constexpr unsigned __int128 toUInt128(const char *s) {
  unsigned __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
constexpr __int128 toInt128(const char *s) {
  if (*s == '-') return -toInt128(s + 1);
  __int128 x = 0;
  for (; *s; ++s) x = x * 10 + (*s - '0');
  return x;
}
unsigned __int128 inUInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toUInt128(buf);
}
__int128 inInt128() {
  static char buf[41];
  scanf("%s", buf);
  return toInt128(buf);
}

void out(unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) putchar(buf[i]);
}
void out(__int128 x) {
  if (x < 0) {
    putchar('-');
    out(-static_cast<unsigned __int128>(x));
  } else {
    out(static_cast<unsigned __int128>(x));
  }
}
std::ostream &operator<<(std::ostream &os, unsigned __int128 x) {
  static char buf[41];
  int len = 0;
  do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10);
  for (int i = len; --i >= 0; ) os << buf[i];
  return os;
}
std::ostream &operator<<(std::ostream &os, __int128 x) {
  if (x < 0) {
    os << '-' << -static_cast<unsigned __int128>(x);
  } else {
    os << static_cast<unsigned __int128>(x);
  }
  return os;
}

#endif  // LIBRA_OTHER_INT128_H_


using Int = __int128;
constexpr Int INF = toInt128("1002003004005006007006005004003002001");

constexpr unsigned MO = 998244353;

char buf[110];

int S;
int N, M;
string K;
vector<int> A, B;
vector<Int> C;


namespace small {
vector<int> run() {
cerr<<"[small::run]"<<endl;
  const int K0 = stoi(K);
  vector<Int> crt(N, INF);
  crt[0] = 0;
  for (int k = 0; k < K0; ++k) {
    vector<Int> nxt(N, INF);
    for (int i = 0; i < M; ++i) {
      chmin(nxt[B[i]], crt[A[i]] + C[i]);
    }
    crt.swap(nxt);
  }
  vector<int> ans(N, -1);
  for (int u = 0; u < N; ++u) if (crt[u] < INF) {
    ans[u] = crt[u] % MO;
  }
  return ans;
}
}  // small


namespace large {
using BigInt = vector<int>;
constexpr int BASE = 10;
BigInt toBigInt(Int a) {
  BigInt ret;
  do {
    ret.push_back(a % BASE);
    a /= BASE;
  } while (a);
  return ret;
}
BigInt toBigInt(const string &s) {
  BigInt ret;
  for (const char c : s) {
    ret.push_back(c - '0');
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
BigInt add(const BigInt &a, const BigInt &b) {
  BigInt c(a.size() + b.size() + 1, 0);
  for (int i = 0; i < (int)a.size(); ++i) c[i] += a[i];
  for (int i = 0; i < (int)b.size(); ++i) c[i] += b[i];
  for (int i = 0; i < (int)c.size() - 1; ++i) {
    if (c[i] >= BASE) {
      c[i + 1] += 1;
      c[i] -= BASE;
    }
  }
  return c;
}
BigInt sub(const BigInt &a, const BigInt &b) {
  BigInt c(a.size() + b.size() + 1, 0);
  for (int i = 0; i < (int)a.size(); ++i) c[i] += a[i];
  for (int i = 0; i < (int)b.size(); ++i) c[i] -= b[i];
  for (int i = 0; i < (int)c.size() - 1; ++i) {
    if (c[i] < 0) {
      c[i + 1] -= 1;
      c[i] += BASE;
    }
  }
  return c;
}
BigInt mul(BigInt p, Int q) {
  Int r = 0;
  for (int i = 0; i < (int)p.size(); ++i) {
    r += p[i] * q;
    p[i] = r % BASE;
    r /= BASE;
  }
  for (; r; ) {
    p.push_back(r % BASE);
    r /= BASE;
  }
  return p;
}
pair<BigInt, int> divmod(BigInt p, int q) {
  long long r = 0;
  for (int i = (int)p.size(); --i >= 0; ) {
    r = r * BASE + p[i];
    p[i] = r / q;
    assert(p[i] < BASE);
    r %= q;
  }
  return make_pair(p, r);
}
int cmp(const BigInt &a, const BigInt &b) {
  for (int i = max((int)a.size(), (int)b.size()); --i >= 0; ) {
    const int aa = (i < (int)a.size()) ? a[i] : 0;
    const int bb = (i < (int)b.size()) ? b[i] : 0;
    if (aa < bb) return -1;
    if (aa > bb) return +1;
  }
  return 0;
}

vector<int> run() {
cerr<<"[large::run]"<<endl;
  vector<vector<int>> G(N);
  for (int i = 0; i < M; ++i) {
    G[A[i]].push_back(i);
  }
  
  using Cyc = pair<pair<Int, int>, int>;
  vector<Cyc> cycs;
  for (int s = 0; s < N; ++s) {
    Int pm = 1;
    int qm = 0;
    vector<Int> crt(N, INF);
    crt[s] = 0;
    for (int k = 1; k <= N; ++k) {
      vector<Int> nxt(N, INF);
      for (int i = 0; i < M; ++i) {
        chmin(nxt[B[i]], crt[A[i]] + C[i]);
      }
      crt.swap(nxt);
      Int p = crt[s];
      int q = k;
      if (p < INF) {
        if (pm * q > p * qm) {
          pm = p;
          qm = q;
        }
      }
    }
    if (qm) {
      cycs.emplace_back(make_pair(pm, qm), s);
    }
  }
  sort(cycs.begin(), cycs.end(), [&](const Cyc &cyc0, const Cyc &cyc1) -> bool {
    return (cyc0.first.first * cyc1.first.second < cyc1.first.first * cyc0.first.second);
  });
  const int cycsLen = cycs.size();
// cerr<<"cycs = "<<cycs<<endl;
  
  const BigInt K0 = toBigInt(K);
  vector<int> can(N, 0);
  vector<BigInt> mns(N);
  for (int j0 = 0, j1 = 0; j0 < cycsLen; j0 = j1) {
    for (; j1 < cycsLen && cycs[j0].first == cycs[j1].first; ++j1) {}
    const Int p = cycs[j0].first.first;
    const int q = cycs[j0].first.second;
    vector<int> ids(N, -2);
    for (int j = 0; j < j0; ++j) {
      ids[cycs[j].second] = -1;
    }
    if (!~ids[0]) {
      continue;
    }
    int U = 0;
    for (int u = 0; u < N; ++u) if (~ids[u]) {
      ids[u] = U++;
    }
    vector<int> on(U, 0);
    for (int j = j0; j < j1; ++j) {
      on[ids[cycs[j].second]] = 1;
    }
// cerr<<"p = "<<p<<", q = "<<q<<", ids = "<<ids<<", on = "<<on<<endl;
    vector<int> as, bs;
    vector<Int> cs;
    for (int i = 0; i < M; ++i) if (~ids[A[i]] && ~ids[B[i]]) {
      as.push_back(ids[A[i]]);
      bs.push_back(ids[B[i]]);
      cs.push_back(C[i]);
    }
    const int m = as.size();
    const auto q0r0 = divmod(K0, q);
    const int r0 = q0r0.second;
    vector<Int> here(U, INF);
    vector<Int> crt(U << 1, INF);
    crt[0 << 1 | on[0]] = 0;
    for (int k = 0; k < U + q * U; ++k) {
      if (k % q == r0) {
        for (int x = 0; x < U; ++x) {
          const Int c = crt[x << 1 | 1];
          if (c < INF) {
            chmin(here[x], c + (N - k / q) * p);
          }
        }
      }
      vector<Int> nxt(U << 1, INF);
      for (int i = 0; i < m; ++i) {
        chmin(nxt[bs[i] << 1 | on[bs[i]]], crt[as[i] << 1 | 0] + cs[i]);
        chmin(nxt[bs[i] << 1 | 1], crt[as[i] << 1 | 1] + cs[i]);
      }
      crt.swap(nxt);
    }
    const BigInt c0 = mul(sub(q0r0.first, toBigInt(N)), p);
    for (int u = 0; u < N; ++u) {
      const int x = ids[u];
      if (~x && here[x] < INF) {
        assert(here[x] >= 0);
        const BigInt c = add(c0, toBigInt(here[x]));
        if (mns[u].empty() || cmp(mns[u], c) > 0) {
          mns[u] = c;
        }
      }
    }
  }
  vector<int> ans(N, -1);
  for (int u = 0; u < N; ++u) if (!mns[u].empty()) {
    ans[u] = divmod(mns[u], MO).second;
  }
  return ans;
}
}  // large


int main() {
  for (int numCases; ~scanf("%d%d", &S, &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d%s", &N, &M, buf);
    K = buf;
    A.resize(M);
    B.resize(M);
    C.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d", &A[i], &B[i]);
      --A[i];
      --B[i];
      C[i] = inInt128();
    }
    
    vector<int> ans;
    if (K.size() <= 9 && stoi(K) <= N * N) {
      ans = small::run();
    } else {
      ans = large::run();
    }
    
    for (int u = 0; u < N; ++u) {
      if (u) printf(" ");
      printf("%d", ans[u]);
    }
#ifdef LOCAL
printf(" ");
#endif
    puts("");
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 4144kb

input:

1
1
100 101 899539897889989959
74 35 910832669819965536
35 85 910832669819965536
85 88 910832669819965536
88 30 910832669819965536
30 58 910832669819965536
58 60 910832669819965536
60 34 910832669819965536
34 8 910832669819965536
8 67 910832669819965536
67 89 910832669819965536
89 32 910832669819965...

output:

395495792 395495781 395495783 395495839 395495793 395495789 395495754 395495832 395495845 395495755 395495823 395495773 395495753 395495800 395495782 395495763 395495847 395495761 395495794 395495791 395495786 395495821 395495798 395495765 395495772 395495770 395495757 395495819 395495843 395495828 ...

result:

ok 100 numbers

Test #2:

score: 0
Accepted
time: 11ms
memory: 3892kb

input:

1
1
100 200 998858598565699977
89 61 596014036562538539
89 84 921297646113897322
61 84 946923234442637386
61 35 641628261157284465
84 35 979893473772327497
84 78 700172488379560611
35 78 963617193748189613
35 54 951598888254521423
78 54 680825215292116806
78 21 737055858973038555
54 21 7491794406112...

output:

590375247 265938345 203065828 597548045 369717762 226160283 377877020 360218254 956162456 408060901 387231165 759578975 67601808 790211315 608425007 343195480 177353482 436533546 717630459 417099733 542227025 861764246 913806375 587268602 989846681 435016550 66609901 817090566 256847656 844441854 94...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 7ms
memory: 4132kb

input:

1
1
100 181 348568663892999968
25 19 990622898175774733
19 94 871060999389241529
94 24 969317630558501400
24 43 908457844888427461
43 52 816088481082287266
52 62 978618931332609685
62 99 761714433396732044
99 85 741344935503895668
85 64 964684335126604843
64 69 988098065125373655
69 31 7506975506815...

output:

916998469 916998469 916998469 76035207 62461893 916998469 389136594 916998469 916998469 173423529 164423356 822964468 626456020 916998469 744111524 916998469 398953850 916998469 342238577 916998469 255074799 784015663 916998469 740933556 587088671 811719512 916998469 916998469 916998469 916998469 14...

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 15ms
memory: 4160kb

input:

1
1
100 189 295064635124730243
18 50 754672892083203214
50 88 962632394366987404
88 15 906700334097319336
15 26 967741400981618572
26 91 996214498763867892
91 35 882157548994344280
35 68 983621159612138407
68 51 563935036482744182
51 75 991205513962219551
75 72 974025375183814852
72 11 7979447663592...

output:

663199381 739882534 663199381 28600701 663199381 944601671 836329160 894091561 629507606 663199381 246830507 663199381 491987421 663199381 802123884 663199381 663199381 663199381 414785533 989396289 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 4...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 11ms
memory: 4172kb

input:

1
254
40 74 997173688939799978
38 6 890721839505665075
6 10 992308491267087930
10 29 960202932780090595
29 20 952827125924298715
20 34 868314670055961466
34 31 756448635709788087
31 14 857625921909632516
14 18 917667459973696862
18 21 985939328882662624
21 1 734882468602343649
1 11 66102593854575036...

output:

177014577 177014577 177014577 885341552 472856470 177014577 363547548 177014577 499847464 653076748 177014577 177014577 177014577 177014577 487939796 177014577 213466543 586729345 244952763 177014577 177014577 177014577 177014577 890105934 177014577 177014577 890105934 177014577 177014577 798890006 ...

result:

ok 3575 numbers

Test #6:

score: 0
Accepted
time: 16ms
memory: 3872kb

input:

1
356
32 47 967844399484634837
4 30 776954643355911997
30 20 811634053140142741
20 22 747630229183579429
22 2 806282875388761050
2 26 719793351534499411
26 17 797537828929335673
17 24 890423236992687627
24 21 970792227007588899
21 8 850078803097295262
8 15 958474507028658347
15 1 972636122087215360
...

output:

890097469 525779071 636798453 776362497 776362497 687961593 158033324 776362497 345910504 380622623 239804834 440670451 137231885 985041116 222869127 137231885 705696901 637534644 347889826 696528073 291555427 146553026 776362497 624486185 137231885 642408114 520519927 137231885 438373632 263924254 ...

result:

ok 4784 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Test #7:

score: 0
Time Limit Exceeded

input:

2
1
300 598 8179377797889487867988994778539839593376697796496698959964978969
1 2 977880533270721156
2 1 977880533270721156
2 3 977880533270721156
3 2 977880533270721156
3 4 977880533270721156
4 3 977880533270721156
4 5 977880533270721156
5 4 977880533270721156
5 6 977880533270721156
6 5 977880533270...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #19:

score: 15
Accepted
time: 7ms
memory: 4172kb

input:

4
1
100 101 6888995999928874698772868926699656683388498575797893294688976887
25 90 495511874996847106
90 84 495511874996847106
84 82 495511874996847106
82 40 495511874996847106
40 97 495511874996847106
97 5 495511874996847106
5 24 495511874996847106
24 16 495511874996847106
16 19 495511874996847106
...

output:

662900138 662900131 662900188 662900147 662900176 662900221 662900152 662900202 662900130 662900140 662900169 662900199 662900128 662900145 662900192 662900178 662900163 662900150 662900179 662900151 662900139 662900180 662900216 662900177 662900170 662900205 662900210 662900183 662900184 662900125 ...

result:

ok 100 numbers

Test #20:

score: 0
Accepted
time: 10ms
memory: 3884kb

input:

4
1
100 200 7298898492397999688666927949888498969897838287679988999656889979
1 68 716477084362826727
1 70 849254955511480878
68 70 965501875328180109
68 27 922798232695217800
70 27 973650788054328171
70 69 992887836560799260
27 69 912347321604310534
27 41 707737334645887057
69 41 939222694708421463
...

output:

59219241 402083566 593666306 414807498 258758770 177911843 190858821 427609509 714942754 794670437 266523695 250908431 280340515 973300594 490891479 435411914 570632298 806776572 581872834 661756417 571008187 273666813 634277068 321782154 962526931 884883598 912195600 389101189 783089343 302322065 7...

result:

ok 100 numbers

Test #21:

score: 0
Accepted
time: 12ms
memory: 3892kb

input:

4
1
100 170 8794888769994978795934858981288869698995675273759827929988816678
85 25 955229927087338794
25 69 715916767824027774
69 8 871119978520194455
8 64 918533454985251428
64 73 928715673496434787
73 95 777734955942460360
95 82 937506435422061091
82 21 972958971354009576
21 81 920481916656974333
...

output:

1429581 1429581 150584952 1429581 1429581 616522075 1429581 1429581 56697037 26641870 455335474 405458157 1429581 119209248 768006956 56697037 1429581 1429581 56697037 825267652 337654936 589008244 691024955 410854366 1429581 1429581 569334223 757829937 1429581 1429581 1429581 387845353 1429581 1429...

result:

ok 100 numbers

Test #22:

score: 0
Accepted
time: 18ms
memory: 4176kb

input:

4
1
100 175 988927424060208873
73 39 871487671517176049
39 12 989592888976857487
12 60 753594598459115125
60 80 804510907944284786
80 87 837728552224523957
87 50 720829671677245259
50 55 955472566241448463
55 56 698073335743612454
56 24 907173313658798936
24 75 812098650937527351
75 23 9749473294852...

output:

120476850 665961545 406533341 950211937 665961545 665961545 665961545 160438797 665961545 860608848 665961545 665961545 665961545 665961545 698344451 665961545 115173142 157625083 665961545 665961545 665961545 817070036 795455857 665961545 615381143 665961545 363716660 579107160 665961545 665961545 ...

result:

ok 100 numbers

Test #23:

score: 0
Accepted
time: 12ms
memory: 4184kb

input:

4
272
40 69 8526848846996917979164958976967645898953979497989749477999798947
16 20 904311791006766339
20 8 861881272650260368
8 38 927651150818983482
38 22 575472375470752507
22 10 995789624005306013
10 17 862458045607914444
17 35 910173488885856948
35 12 897609723109586512
12 23 970232607197909774
...

output:

631006282 189710405 538148249 980737927 538148249 223767537 200756370 844883815 538148249 538148249 506622768 538148249 278823150 381947526 538148249 594558624 538148249 751430936 664913832 538148249 961366366 945739792 646619933 538148249 538148249 538148249 538148249 831302 107422344 538148249 118...

result:

ok 3782 numbers

Test #24:

score: 0
Accepted
time: 13ms
memory: 3848kb

input:

4
367
32 64 7694675676969676989727597922979586548768678479696836977677459878
26 1 948535512091890169
1 28 927579818325689242
28 18 869862583518920980
18 24 916474447302009020
24 23 592009716422157884
23 12 932781568469333631
12 17 906790845067818370
17 16 733495190715963829
16 5 948217995091033642
5...

output:

242947009 937164220 269122924 473901869 812915310 815200847 138502251 269122924 269122924 269122924 269122924 269122924 269122924 790732730 269122924 269122924 423399215 858100602 269122924 259562134 269122924 613550676 269122924 242947009 269122924 269122924 210817778 269122924 269122924 269122924 ...

result:

ok 4886 numbers

Subtask #5:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #25:

score: 15
Accepted
time: 139ms
memory: 4044kb

input:

5
1
300 301 969767789936486493
164 284 964646444984408140
284 241 964646444984408140
241 281 964646444984408140
281 138 964646444984408140
138 242 964646444984408140
242 112 964646444984408140
112 217 964646444984408140
217 170 964646444984408140
170 31 964646444984408140
31 300 964646444984408140
3...

output:

562333388 562333371 562333450 562333457 562333181 562333366 562333433 562333276 562333204 562333354 562333361 562333374 562333436 562333405 562333369 562333286 562333360 562333318 562333396 562333251 562333480 562333220 562333333 562333460 562333359 562333295 562333293 562333335 562333402 562333226 ...

result:

ok 300 numbers

Test #26:

score: 0
Accepted
time: 201ms
memory: 4260kb

input:

5
1
300 600 798876399989994933
7 196 978372754397099680
7 150 850366341978113658
196 150 741178931696536015
196 241 918555502737513857
150 241 755464499814711391
150 249 715712249601810459
241 249 834572033520725671
241 172 840925258261612828
249 172 765221764158211117
249 92 987381804975984305
172 ...

output:

103349950 4999241 142118823 400506111 885559364 196293932 888044807 431387396 656847997 382995767 154772964 775074870 360166602 822043040 871256466 771891985 42704853 943406678 158027440 486796258 972364206 191106105 158852164 825942858 973808447 981369554 98907807 66904970 935447293 466970182 66575...

result:

ok 300 numbers

Test #27:

score: 0
Accepted
time: 657ms
memory: 3928kb

input:

5
1
300 319 999568963877948597
127 165 930758488326418731
165 155 912956207532166981
155 28 930375923771407137
28 174 952825751389557214
174 170 969510032281804566
170 241 896480622553779223
241 54 857133548480482773
54 22 748966877674282581
22 105 992399083086354199
105 73 833098032662288489
73 199...

output:

615687095 22340881 220606255 926757569 403722771 339583612 218798352 675170360 910785402 527927433 468935392 80089701 112798914 308829476 977528530 484462850 559184887 21739752 111487269 309000604 260902067 244633941 296132705 230226837 668779298 283618195 103042591 779688636 992598043 560518243 807...

result:

ok 300 numbers

Test #28:

score: 0
Accepted
time: 281ms
memory: 3996kb

input:

5
1
300 548 824591615686303801
277 294 884790950503796190
294 241 928062180696957669
241 164 997854303092696029
164 296 922799499949016142
296 248 944988731600431360
248 153 831789824022472151
153 180 666918059700566083
180 87 790575536963511661
87 285 804674576894023412
285 211 822686794867787872
2...

output:

278188366 278188366 278188366 278188366 278188366 50768692 278188366 278188366 278188366 278188366 888601612 278188366 371280094 739457050 790269377 850776214 278188366 278188366 278188366 18157734 278188366 278188366 278188366 811551034 356306457 730311889 608326520 278188366 109322194 278188366 27...

result:

ok 300 numbers

Test #29:

score: 0
Accepted
time: 327ms
memory: 3988kb

input:

5
40
120 131 679889999068592637
118 98 812545734198160781
98 91 917010970269512244
91 95 698053144863731543
95 14 628901820405095492
14 22 889645699347522207
22 51 871704747332576532
51 19 994723476638446914
19 108 935669854949015658
108 83 944628276409310798
83 6 997623504444369992
6 44 89978656209...

output:

347797689 625661551 663318864 430007740 779572483 678295713 604524795 482364258 563274534 733628768 109065455 813167359 237637495 314851932 792047890 731351621 209595139 105858678 353663190 171125513 429932280 382442950 478291233 424842463 792632068 72912215 20364781 716856724 782743587 623493496 35...

result:

ok 3150 numbers

Test #30:

score: 0
Accepted
time: 334ms
memory: 3908kb

input:

5
5333
96 163 896598775993796678
48 22 988628974528111232
22 79 974327267551042014
79 89 963371577075408650
89 35 977281141965145271
35 83 933480640131723472
83 71 671664664777649600
71 6 618937617718672760
6 18 899457718948743597
18 34 950491723718783148
34 50 977014890463222654
50 25 6638914519516...

output:

301347522 422213537 486604400 730721865 21694591 422213537 422213537 254465456 422213537 422213537 611991526 115365870 422213537 422213537 422213537 422213537 868835950 422213537 422213537 422213537 422213537 422213537 422213537 212714492 422213537 966025026 459165854 321559202 422213537 422213537 2...

result:

ok 72861 numbers

Subtask #6:

score: 0
Skipped

Dependency #3:

0%