QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#124024#90. Fishing Gamesomethingnew#0 104ms51280kbC++203.8kb2023-07-14 04:06:152024-07-04 00:38:52

Judging History

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

  • [2024-07-04 00:38:52]
  • 评测
  • 测评结果:0
  • 用时:104ms
  • 内存:51280kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-14 04:06:15]
  • 提交

answer

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
int mod = 1e9 + 7;
int dp[300][300][300];
int calced[300][300][300];//011 101 110
int pls(int a, int b) {
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}
int mult(int a, int b) {
    return 1ll * a * b % mod;
}
int getv(int a, int b, int c) {
    if (calced[a][b][c])
        return dp[a][b][c];
    if (a == 0 and b == 0 and c == 0)
        return 1;
    calced[a][b][c] = 1;
    vector<pair<int, int>> step1 = {{1, 0}, {2, -1}};
    vector<pair<int, int>> step2 = {{0, -1}, {2, 1}};
    vector<pair<int, int>> step3 = {{0, 2}, {1, -1}};
    for (auto op1 : step1) {
        array<int, 3> abac = {a, b, c};
        int reba = 1;
        bool okidoki = 0;
        if (abac[op1.first]) {
            reba = mult(reba, abac[op1.first]);
            abac[op1.first]--;
            if (op1.second != -1)
                abac[op1.second]++;
            else
                okidoki = 1;
            //cout << a << ' ' << b << ' ' << c << "->" << abac[0] << ' ' << abac[1] << ' ' << abac[2] << endl;
            for (auto op2 : step2) {
                array<int, 3> abaccop = abac;
                bool okidokicop = okidoki;
                if (abaccop[op2.first]) {
                    reba = mult(reba, abaccop[op2.first]);
                    abaccop[op2.first]--;
                    if (op2.second != -1)
                        abaccop[op2.second]++;
                    else
                        okidokicop = 1;
                    //cout << a << ' ' << b << ' ' << c << "->" << abac[0] << ' ' << abac[1] << ' ' << abac[2] << endl;
                    for (auto op3 : step3) {
                        array<int, 3> abaccopcop = abaccop;
                        bool okidokicopcop = okidokicop;
                        if (abaccopcop[op3.first]) {
                            reba = mult(reba, abaccopcop[op3.first]);
                            abaccopcop[op3.first]--;
                            if (op3.second != -1)
                                abaccopcop[op3.second]++;
                            else
                                okidokicopcop = 1;
                            //cout << a << ' ' << b << ' ' << c << "->" << abaccopcop[0] << ' ' << abaccopcop[1] << ' ' << abaccopcop[2] << endl;
                            if (okidokicopcop)
                                dp[a][b][c] = pls(dp[a][b][c], mult(getv(abaccopcop[0], abaccopcop[1], abaccopcop[2]), reba));
                        }
                    }
                }
            }
        }
    }
    return dp[a][b][c];
}
int n;
void solve() {
    vector<vector<int>> beba(3 * n);
    for (int i = 0; i < 2 * n; ++i) {
        int x;
        cin >> x;
        x--;
        beba[x].push_back(0);
    }
    for (int i = 0; i < 2 * n; ++i) {
        int x;
        cin >> x;
        x--;
        beba[x].push_back(1);
    }
    for (int i = 0; i < 2 * n; ++i) {
        int x;
        cin >> x;
        x--;
        beba[x].push_back(2);
    }
    int a = 0, b = 0, c = 0;
    for (int i = 0; i < 3 * n; ++i) {
        sort(all(beba[i]));
        if (beba[i][0] == 1 and beba[i][1] == 2)
            a++;
        if (beba[i][0] == 0 and beba[i][1] == 2)
            b++;
        if (beba[i][0] == 0 and beba[i][1] == 1)
            c++;
    }
    cout << getv(a, b, c) << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> n >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
6 1 5 2
1 6 4 2
3 4 5 3
6 3 1 5
2 3 5 6
2 4 4 1
1 2 3 4
3 4 5 6
1 2 5 6

output:

1026
1026
178848

result:

wrong answer 1st lines differ - expected: '690', found: '1026'

Test #2:

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

input:

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

output:

47270880
178848
925617924
178848
925617924

result:

wrong answer 1st lines differ - expected: '920808', found: '47270880'

Test #3:

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

input:

10 5
15 22 9 24 13 11 7 25 21 14 3 5 4 26 19 26 18 29 16 29
16 7 13 30 17 1 4 15 23 9 12 20 22 2 23 18 5 3 10 21
12 30 14 28 27 11 24 8 10 28 17 27 2 20 1 25 6 19 8 6
19 15 27 9 16 21 14 10 19 15 12 11 2 7 16 28 26 25 18 18
12 24 13 29 13 14 1 1 20 29 22 17 3 23 11 28 20 17 5 10
4 24 3 6 4 5 21 22 2...

output:

491998251
339427414
679127999
746484318
433183473

result:

wrong answer 1st lines differ - expected: '169430774', found: '491998251'

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 5800kb

input:

20 5
26 19 51 35 32 56 13 57 27 9 44 35 34 58 42 12 59 12 8 33 59 16 1 17 11 50 60 28 34 7 33 1 15 8 32 11 29 22 27 52
9 24 15 2 45 19 56 39 28 18 21 3 14 41 6 18 23 25 6 26 23 49 52 17 2 42 10 16 41 31 4 54 43 29 30 46 55 24 49 44
10 21 20 55 20 60 14 4 37 54 45 48 31 5 47 3 5 40 36 36 38 53 7 43 4...

output:

143855020
462796885
830664376
745274198
917542649

result:

wrong answer 1st lines differ - expected: '147852189', found: '143855020'

Test #5:

score: 0
Wrong Answer
time: 8ms
memory: 16176kb

input:

50 10
103 51 39 35 6 66 124 140 131 19 117 97 47 98 14 101 60 41 99 140 94 58 132 30 128 116 44 41 104 7 1 90 75 37 14 95 89 45 116 79 90 86 138 11 7 102 43 87 29 110 127 127 84 26 62 128 107 56 136 47 64 42 124 149 119 71 48 100 40 81 59 11 59 83 62 91 55 4 146 5 73 46 145 117 75 24 20 26 16 97 122...

output:

224460724
857432813
562085648
555412829
878975438
641326893
250339154
234177689
346466651
799780865

result:

wrong answer 1st lines differ - expected: '417911208', found: '224460724'

Test #6:

score: 0
Wrong Answer
time: 22ms
memory: 21504kb

input:

60 10
180 96 39 136 47 63 77 105 74 67 142 122 70 72 137 143 155 95 156 105 121 37 81 3 159 167 139 130 152 180 88 148 149 114 31 43 112 146 127 84 90 75 27 2 46 128 178 116 69 83 117 135 173 177 118 129 34 127 94 40 174 150 56 99 159 116 43 44 59 32 163 175 131 54 113 50 132 50 83 94 149 88 27 161 ...

output:

167749780
733702109
924840565
286128257
517966235
879954741
218713916
135948947
711188218
195986361

result:

wrong answer 1st lines differ - expected: '718107834', found: '167749780'

Test #7:

score: 0
Wrong Answer
time: 40ms
memory: 27700kb

input:

70 10
78 164 105 187 88 118 8 96 82 143 38 127 27 93 18 171 19 158 112 91 179 17 40 15 99 205 113 19 186 16 26 82 4 41 193 5 110 79 201 106 161 59 183 196 123 127 69 37 117 130 88 141 96 93 149 113 176 206 46 195 35 178 102 111 155 41 25 148 150 179 185 61 166 136 118 176 46 50 61 84 124 150 112 185...

output:

960769947
49254091
86038045
875269794
895284564
752946797
229116662
868795708
735208653
172657216

result:

wrong answer 1st lines differ - expected: '574244039', found: '960769947'

Test #8:

score: 0
Wrong Answer
time: 52ms
memory: 34904kb

input:

80 10
125 87 139 196 191 41 58 194 2 175 150 76 18 87 1 40 180 166 13 119 159 123 210 135 61 224 142 149 222 216 197 113 234 194 9 231 96 71 198 176 98 36 24 185 235 157 80 122 226 187 42 240 154 171 25 218 195 198 124 50 113 32 91 119 45 141 53 12 74 121 158 96 180 116 145 22 142 133 88 182 16 124 ...

output:

152249917
174534732
188077970
185402641
568837031
708473232
573625160
567740052
685153192
484745366

result:

wrong answer 1st lines differ - expected: '182989152', found: '152249917'

Test #9:

score: 0
Wrong Answer
time: 81ms
memory: 43160kb

input:

90 10
42 170 5 215 133 153 104 85 9 164 157 42 87 108 64 161 205 168 228 216 257 81 163 68 195 99 234 136 231 142 127 149 86 182 224 219 80 125 7 230 256 41 204 125 251 77 86 29 28 204 55 15 30 35 174 53 269 23 240 127 262 199 260 232 259 46 80 43 49 169 233 88 192 27 217 186 47 185 228 249 63 245 2...

output:

487392660
691604024
397417167
899336169
447153634
462623072
242872487
236608
415200605
31489677

result:

wrong answer 1st lines differ - expected: '896986561', found: '487392660'

Test #10:

score: 0
Wrong Answer
time: 104ms
memory: 51280kb

input:

99 10
243 69 109 28 151 100 296 2 258 112 25 206 181 148 21 246 12 84 254 250 91 248 46 14 183 162 38 82 130 48 20 150 139 247 283 24 29 93 191 105 129 38 131 87 147 166 22 297 297 71 232 185 106 123 291 15 63 101 286 214 224 29 187 154 215 292 226 223 225 55 23 170 165 238 137 113 203 79 21 217 289...

output:

797933009
548732605
175018245
582212551
585865078
71532260
954267859
249974510
877385077
819667782

result:

wrong answer 1st lines differ - expected: '842856263', found: '797933009'