QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181887#6321. Five Med Sumhos_lyricAC ✓104ms8992kbC++144.6kb2023-09-17 02:59:032023-09-17 02:59:04

Judging History

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

  • [2023-09-17 02:59:04]
  • 评测
  • 测评结果:AC
  • 用时:104ms
  • 内存:8992kb
  • [2023-09-17 02:59:03]
  • 提交

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 <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 = 998244353;
using Mint = ModInt<MO>;


int N;
vector<int> A[5];

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int i = 0; i < 5; ++i) {
      A[i].resize(N);
      for (int j = 0; j < N; ++j) {
        scanf("%d", &A[i][j]);
      }
    }
    
    vector<pair<int, int>> es(5 * N);
    for (int i = 0; i < 5; ++i) for (int j = 0; j < N; ++j) {
      es[i * N + j] = make_pair(A[i][j], i);
    }
    sort(es.begin(), es.end());
    
    Mint ans = 0;
    int cnt[5] = {};
    for (const auto &e : es) {
      const int i = e.second;
      for (int p = 0; p < 5; ++p) for (int q = p + 1; q < 5; ++q) if (i != p && i != q) {
        Mint prod = e.first;
        for (int r = 0; r < 5; ++r) if (i != r) {
          prod *= ((p == r || q == r) ? cnt[r] : (N - cnt[r]));
        }
        ans += prod;
      }
      ++cnt[i];
    }
    printf("%u\n", ans.x);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3680kb

input:

1
1
2
3
4
5

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2

output:

486

result:

ok 1 number(s): "486"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

1
0
0
0
0
0

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

1
823489320
406308599
710963770
183707427
192930969

output:

406308599

result:

ok 1 number(s): "406308599"

Test #5:

score: 0
Accepted
time: 57ms
memory: 8876kb

input:

100000
998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998244352 998...

output:

232107959

result:

ok 1 number(s): "232107959"

Test #6:

score: 0
Accepted
time: 104ms
memory: 8992kb

input:

100000
941365774 515755727 771694833 432704750 529994171 330466913 325661522 333413875 436073827 121697958 699219049 585050633 411517180 595255256 412480566 467584076 962222606 36737488 698035865 756254706 766699617 808303798 979551378 892736022 201788819 368809230 430513494 698446576 708006287 9010...

output:

839818183

result:

ok 1 number(s): "839818183"

Test #7:

score: 0
Accepted
time: 74ms
memory: 8908kb

input:

100000
617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617683563 617...

output:

369063343

result:

ok 1 number(s): "369063343"

Test #8:

score: 0
Accepted
time: 69ms
memory: 8888kb

input:

100000
694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694316732 694...

output:

853878290

result:

ok 1 number(s): "853878290"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3700kb

input:

40
291943223 76965000 742149515 719504220 193679941 604221855 162265443 555855325 227170005 598840055 718317291 477136423 349477987 87350781 304495262 803558063 481746961 220606831 75346783 980264511 377148377 503749474 416272431 555163314 234434836 985496058 61486495 385112773 900108326 613617263 3...

output:

8320781

result:

ok 1 number(s): "8320781"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

1006
111206925 856835698 902245367 466317921 719656505 317083259 833534112 904148057 155796080 145114713 524253430 126212646 821906991 213923821 272207023 239755161 528226795 3289176 961671477 109711486 148342457 798978937 255300730 913775129 559259897 84385779 920126713 789823141 420473624 12599689...

output:

433021433

result:

ok 1 number(s): "433021433"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3684kb

input:

4
667317564 917203256 923726278 682988748
42573638 396112629 714939326 356213499
398882327 113769044 806547918 499754769
359490026 297439068 327401562 124636848
12696962 740015762 490679224 466447156

output:

479267599

result:

ok 1 number(s): "479267599"

Test #12:

score: 0
Accepted
time: 78ms
memory: 8212kb

input:

85575
15580118 396461091 363839961 180628199 648567511 586917199 642501604 442376978 781806998 946462389 163082505 188706828 929830209 129597799 338162421 164925252 163654314 443518445 652556157 33297164 937911024 202088170 422738775 317422544 224628106 121941441 625021658 182121323 705833759 514889...

output:

39269267

result:

ok 1 number(s): "39269267"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

1
129197166
650321672
776268378
630702532
255665333

output:

630702532

result:

ok 1 number(s): "630702532"

Test #14:

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

input:

14479
723244656 243625856 901627013 215212278 214635138 313852039 65497879 978301156 903229291 712176295 199128090 701249328 1448335 590625956 124759227 922493946 766399624 868914139 405785256 970624181 734574584 42289510 563385705 107016439 375980988 953793109 729203481 106042934 669287799 14881969...

output:

629267517

result:

ok 1 number(s): "629267517"

Test #15:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

5
607233096 743979578 813011396 447352746 645781471
809103564 424341877 729941720 579098122 580780363
782751068 33619189 825317675 836152983 848806245
118629851 209116293 74533906 148086157 579120441
167808930 963539245 919625637 688283940 502269444

output:

386209470

result:

ok 1 number(s): "386209470"

Test #16:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

1
364973850
327577071
499465139
676457669
88221889

output:

364973850

result:

ok 1 number(s): "364973850"

Test #17:

score: 0
Accepted
time: 4ms
memory: 3864kb

input:

6075
939138269 208314662 443075791 977257987 441376272 578739562 453636008 14148322 240699588 558197629 788883415 603869816 313525499 844524514 792075762 335728697 456346173 243007834 388025750 295984985 547885950 239809452 269419043 444128655 878174025 742669928 599837177 964838616 459322784 973533...

output:

619451467

result:

ok 1 number(s): "619451467"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

603
483521281 492005222 490463545 8122599 40776056 312497958 651405065 946724944 817420851 581901179 628040997 724810423 364173981 421345689 507918435 38337864 682061867 587397051 271982909 219850359 953615385 600689369 508690846 512023671 669635881 385416345 599945525 967642737 689034485 409911495 ...

output:

507421862

result:

ok 1 number(s): "507421862"

Test #19:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

3585
214361583 246350520 341779714 186379690 888009980 157076299 847425179 122449792 879388636 253688983 374515286 347165381 714648940 969357011 68976041 550345181 434964967 482519696 241431319 340633056 702478470 28803871 490683595 233598652 875501377 842875818 919882108 894693009 315270386 2340331...

output:

830370055

result:

ok 1 number(s): "830370055"

Test #20:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

4
466406842 490284999 510949675 998225556
887314987 398911047 898477315 406258795
234871101 43541612 507998027 642868537
379189114 493000867 7085322 345442114
887559464 757836322 260355392 474113675

output:

70168178

result:

ok 1 number(s): "70168178"

Test #21:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

14
23164170 105748089 925266952 482507686 446471948 258833334 133519775 671345064 703359704 773801727 599005225 268859964 83921427 756710156
321388078 211819992 27947358 731090226 920228660 857890392 770666813 793557343 566614125 969897352 24168747 957041238 373197064 723023339
121226044 371082418 6...

output:

667287659

result:

ok 1 number(s): "667287659"

Test #22:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

7
634371899 953313131 695161414 610474500 661740500 667897882 993186494
121134472 752511175 601822635 840116703 553204077 284640002 717013031
528314951 658308794 18013153 422523842 946504548 879517628 191605233
660232111 399456681 94571317 534467887 6898493 39112016 296353933
37070977 33172948 56146...

output:

938868088

result:

ok 1 number(s): "938868088"

Test #23:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

17
440336064 342105234 727570014 791004026 497684904 731280341 410806332 700740852 962642675 9645927 775143908 420195230 603984541 495780553 896508084 448854388 300826276
600111551 481508297 748651176 577749738 998156277 940141124 597600378 836026096 117627686 653993089 86009261 826415600 941051751 ...

output:

145451478

result:

ok 1 number(s): "145451478"

Test #24:

score: 0
Accepted
time: 25ms
memory: 4524kb

input:

21542
396098157 487026935 434801026 396172288 927478464 833073931 6931909 759717478 509228995 75598154 650508496 915840874 55415080 139538855 364386848 955523295 978890528 655924554 392439031 439641364 528529585 754994405 35415413 411979904 616057215 656273448 429024600 739376906 943241097 719258030...

output:

696642220

result:

ok 1 number(s): "696642220"

Test #25:

score: 0
Accepted
time: 24ms
memory: 4424kb

input:

21140
965507003 836471086 500161537 228388384 206438610 673640617 498128021 55915367 332895676 974652076 79796313 859784734 876301495 723226185 430089142 935161565 928605991 463579334 597902620 859348408 739220960 624245045 139100985 231218701 207342805 42302087 641207379 935542757 981037403 3105553...

output:

455695519

result:

ok 1 number(s): "455695519"

Test #26:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

61
485562237 875365479 831085270 52557335 603116597 633944672 940024862 715085836 138814528 757612274 676551741 42577057 807054416 298488937 473123170 742819996 212629055 913057277 170630608 292389357 653267424 217047889 713232033 262398254 352886845 947701140 203692118 610808367 574307134 765935262...

output:

101448138

result:

ok 1 number(s): "101448138"

Test #27:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

1
433262850
25078341
734627098
839015568
321649009

output:

433262850

result:

ok 1 number(s): "433262850"

Test #28:

score: 0
Accepted
time: 5ms
memory: 3904kb

input:

8871
260950882 3182522 910771724 676405021 598023636 547063867 456809596 17105936 505008482 528747147 117231005 951651131 967863378 363390286 379505167 945712673 92610769 942306688 531666736 639683577 264644954 708403994 155922649 705058185 597117775 79664489 282382508 955116331 717070566 331018978 ...

output:

173014762

result:

ok 1 number(s): "173014762"