QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#748230#9562. 欧伊昔SunsetGlow950 71ms10436kbC++143.1kb2024-11-14 19:46:292024-11-14 19:46:29

Judging History

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

  • [2024-11-14 19:46:29]
  • 评测
  • 测评结果:0
  • 用时:71ms
  • 内存:10436kb
  • [2024-11-14 19:46:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int RDX = 3;
const int MXR = 6;
const int MXN = 12;
const int MXL = 180000;
const int MXC = 60500000;
int N, table[RDX][RDX], arr[MXL], brr[MXL], mp[MXL], rmp[MXC];
long long ans[MXL], ta[MXC], tb[MXC], crr[MXL], tmp[MXR];
int scnt[RDX], spv, R(1), pw3[MXN], pwr[MXN];
int coa[RDX][MXR], cob[RDX][MXR], coc[MXR][RDX];

void work(int *a, int *b, long long *c) {
  for (int i(0); i != pwr[N - 1]; ++i)
    ta[i] = a[i], tb[i] = b[i];
  for (int i(0); i != N - 1; ++i) {
    for (int j(0); j != pwr[N - 1]; ++j) {
      if (j / pwr[i] % R) continue;
      for (int k(0); k != RDX; ++k)
        for (int l(0); l != R; ++l)
          tmp[l] += ta[j + k * pwr[i]] * coa[k][l];
      for (int k(0); k != R; ++k)
        ta[j + k * pwr[i]] = tmp[k], tmp[k] = 0;
      for (int k(0); k != RDX; ++k)
        for (int l(0); l != R; ++l)
          tmp[l] += tb[j + k * pwr[i]] * cob[k][l];
      for (int k(0); k != R; ++k)
        tb[j + k * pwr[i]] = tmp[k], tmp[k] = 0;
    }
  }
  for (int i(0); i != pwr[N - 1]; ++i) ta[i] *= tb[i], tb[i] = 0;
  for (int i(0); i != N - 1; ++i) {
    for (int j(0); j != pwr[N - 1]; ++j) {
      if (j / pwr[i] % R) continue;
      for (int k(0); k != R; ++k)
        for (int l(0); l != RDX; ++l)
          tmp[l] += ta[j + k * pwr[i]] * coc[k][l];
      for (int k(0); k != R; ++k)
        ta[j + k * pwr[i]] = tmp[k], tmp[k] = 0;
    }
  }
  for (int i(0); i != pwr[N - 1]; ++i)
    c[i] += ta[i];
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  for (int i(0); i != RDX; ++i)
    for (int j(0); j != RDX; ++j)
      cin >> table[i][j], ++scnt[table[i][j]];
  spv = max_element(scnt, scnt + RDX) - scnt;
  coc[0][spv] = 1;
  for (int i(0); i != RDX; ++i) {
    coa[i][0] = cob[i][0] = 1;
    if (i == spv) continue;
    for (int j(0); j != RDX; ++j) scnt[j] = 0;
    for (int j(0); j != RDX; ++j)
      for (int k(0); k != RDX; ++k) scnt[k] += table[j][k] == i;
    bool typ(*max_element(scnt, scnt + RDX) <= 1);
    for (int j(0); j != RDX; ++j) {
      bool ex(false);
      for (int k(0); k != RDX; ++k) {
        if ((typ ? table[j][k] : table[k][j]) == i)
          (typ ? cob : coa)[k][R] = 1, ex = true;
      }
      if (ex) {
        (typ ? coa : cob)[j][R] = 1;
        coc[R][i] = 1;
        coc[R][spv] = -1;
        ++R;
      }
    }
  }
  R = max(R, RDX);
  assert(R <= MXR);
   
  cin >> N;
  pw3[0] = pwr[0] = 1;
  for (int i(1); i <= N; ++i) pwr[i] = pwr[i - 1] * R, pw3[i] = pw3[i - 1] * 3;
  for (int i(0); i != pw3[N]; ++i) cin >> arr[i];
  for (int i(0); i != pw3[N]; ++i) cin >> brr[i];
  for (int i(0); i != pw3[N - 1]; ++i) mp[i] = mp[i / RDX] * R + i % RDX;
  for (int i(0); i != pwr[N - 1]; ++i)
    rmp[i] = (i % R >= RDX || pwr[i / R] == -1 ? -1 :
              rmp[i / R] * RDX + i % R);
  for (int ad(0); ad != RDX; ++ad) {
    for (int bd(0); bd != RDX; ++bd) {
      work(arr + ad * pw3[N - 1], brr + bd * pw3[N - 1],
           crr + table[ad][bd] * pw3[N - 1]);
    }
  }
  for (int i(0); i != pw3[N]; ++i) {
    cout << crr[i] << ' ';
  }
  cout << endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

0 1 2
1 2 0
2 0 1
1
7 1 5
8 4 5

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 5
Accepted
time: 1ms
memory: 9748kb

input:

1 2 1
2 0 0
1 0 0
1
8 9 3
1 6 1

output:

84 19 57 

result:

ok single line: '84 19 57 '

Test #7:

score: 0
Wrong Answer
time: 1ms
memory: 7772kb

input:

1 2 1
2 0 0
1 0 0
3
0 9 8 8 9 2 6 5 1 7 2 9 8 8 7 9 1 9 8 0 3 6 8 6 6 1 6
2 7 1 0 3 4 9 1 7 3 1 3 3 6 1 4 6 7 3 9 5 0 6 5 6 6 8

output:

702 471 465 0 0 484 561 273 0 896 883 860 382 0 892 175 211 0 724 994 521 269 0 447 220 219 0 

result:

wrong answer 1st lines differ - expected: '2070 1350 930 936 1077 524 774...715 415 569 372 227 360 144 155', found: '702 471 465 0 0 484 561 273 0 ...24 994 521 269 0 447 220 219 0 '

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 20
Accepted
time: 1ms
memory: 7700kb

input:

1 1 1
0 0 0
1 1 1
1
6 2 1
3 1 5

output:

18 63 0 

result:

ok single line: '18 63 0 '

Test #12:

score: 0
Wrong Answer
time: 1ms
memory: 7780kb

input:

1 1 0
0 0 1
0 0 1
3
4 6 4 5 6 8 7 7 4 0 0 9 1 0 9 0 8 5 3 4 0 0 4 2 3 5 1
4 2 5 5 6 2 4 6 5 2 5 0 0 4 0 6 3 8 1 2 3 7 0 6 8 4 8

output:

1229 991 0 0 1030 803 0 0 0 1116 954 0 0 938 765 0 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer 1st lines differ - expected: '1776 1049 0 1615 1167 0 0 0 0 ... 1202 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '1229 991 0 0 1030 803 0 0 0 11...38 765 0 0 0 0 0 0 0 0 0 0 0 0 '

Subtask #4:

score: 0
Wrong Answer

Test #16:

score: 30
Accepted
time: 1ms
memory: 7748kb

input:

1 1 1
0 0 1
1 1 0
1
1 0 9
8 1 9

output:

81 99 0 

result:

ok single line: '81 99 0 '

Test #17:

score: 0
Wrong Answer
time: 0ms
memory: 9696kb

input:

0 0 1
0 0 1
1 1 0
3
7 6 2 7 7 9 5 5 6 0 5 7 5 8 1 0 6 0 9 3 3 5 1 8 2 2 1
8 5 9 1 0 0 0 4 9 1 4 3 2 5 1 9 2 2 8 7 6 8 7 3 9 1 0

output:

2314 2004 0 0 1567 1275 0 0 0 1914 1567 0 0 994 777 0 0 0 0 0 0 0 0 0 0 0 0 

result:

wrong answer 1st lines differ - expected: '2402 1847 0 1687 1320 0 0 0 0 ...2 955 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '2314 2004 0 0 1567 1275 0 0 0 ...94 777 0 0 0 0 0 0 0 0 0 0 0 0 '

Subtask #5:

score: 0
Wrong Answer

Test #21:

score: 10
Accepted
time: 9ms
memory: 10004kb

input:

0 2 2
1 1 1
0 1 1
9
2 7 2 7 4 5 9 7 9 6 8 4 0 6 3 3 6 3 0 5 2 3 7 6 7 8 3 6 1 1 6 9 9 2 7 2 1 2 8 2 9 3 5 0 5 7 1 2 3 1 4 8 0 4 3 4 2 8 8 4 2 9 3 7 1 1 6 6 4 0 9 6 5 8 8 1 3 8 7 3 0 4 3 8 7 0 0 7 6 4 3 6 0 2 3 3 6 5 0 5 9 8 6 1 0 4 7 8 2 4 7 4 8 6 9 6 3 5 1 8 0 1 4 7 0 0 1 2 7 7 0 5 5 3 8 2 7 8 9 8 ...

output:

18440 36200 13740 21447 61214 26652 5665 22043 8496 29112 57852 21456 67960 192140 70368 29748 86008 35360 8912 17724 6564 29955 76168 32916 11361 32499 12720 18364 76188 36444 42131 187672 92455 14190 70759 31583 70268 162402 69612 200033 446344 181086 87111 192351 80214 28253 57785 24432 98560 188...

result:

ok single line: '18440 36200 13740 21447 61214 ...76 81555 44223 4512 28578 4596 '

Test #22:

score: 10
Accepted
time: 1ms
memory: 7832kb

input:

0 1 2
1 0 0
1 0 1
1
0 9 2
9 7 1

output:

86 101 0 

result:

ok single line: '86 101 0 '

Test #23:

score: 10
Accepted
time: 1ms
memory: 7704kb

input:

2 2 0
0 0 1
0 0 1
5
7 8 3 5 6 1 5 0 1 9 7 3 0 7 0 9 4 7 2 3 1 4 9 4 6 4 9 6 9 8 9 7 8 4 1 4 1 7 7 3 9 3 6 6 8 2 4 3 4 2 4 7 9 9 7 3 0 7 2 6 8 2 3 7 3 2 5 8 9 6 8 4 2 1 1 6 8 6 2 9 8 3 8 5 2 1 8 3 1 3 9 8 7 6 2 9 3 2 1 7 4 8 3 3 8 0 4 5 1 5 2 2 7 3 1 9 4 4 7 1 7 6 5 0 6 8 9 3 3 8 8 6 5 7 6 3 6 0 0 6 ...

output:

65779 30392 21974 25288 12458 7720 24011 9803 10740 28954 12095 10240 11185 4960 3594 10287 3557 5314 24799 11548 8039 9011 4444 2949 10517 4941 3339 27387 10507 10096 12176 3831 4214 8780 3028 4385 14146 4070 5339 5293 2110 1761 4031 1015 2464 10147 3888 3541 4242 1177 1726 3898 1645 1300 24473 122...

result:

ok single line: '65779 30392 21974 25288 12458 ... 1803 912 352 590 2096 891 973 '

Test #24:

score: 0
Wrong Answer
time: 71ms
memory: 10436kb

input:

2 1 1
0 2 2
2 1 1
8
1 1 0 0 2 9 1 0 3 7 7 3 9 2 5 0 1 4 3 3 4 3 0 1 4 5 3 4 2 7 6 3 7 6 5 1 5 6 4 0 8 3 1 3 6 2 0 2 4 7 8 6 3 1 7 0 1 3 1 2 8 9 3 3 0 4 6 0 5 6 1 0 8 9 9 4 4 8 0 7 0 8 3 1 1 1 3 0 8 4 3 8 7 2 8 5 6 4 3 7 7 9 5 8 5 2 6 0 7 5 2 1 9 7 4 8 2 0 4 2 1 0 4 0 0 6 7 1 6 4 9 2 9 1 7 1 3 0 4 3 ...

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 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 0 0 0 0 0 0 0 ...

result:

wrong answer 1st lines differ - expected: '20 128 104 64 304 280 72 432 3... 1334228 322796 1305543 1304871', found: '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 '

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%