QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #528799 | #1263. Keep It Cool | hztmax0 | AC ✓ | 95ms | 17848kb | C++14 | 1.0kb | 2024-08-23 21:53:15 | 2024-08-23 21:53:16 |
Judging History
answer
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
const int N = 12, S = 3628800 + 5;
const int Mod = 998244353;
int n, m;
int a[N * N], b[N * N], c[N * N], d[N * N], p[N], f[S], fac[N], pos[N];
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i;
}
iota(p + 1, p + n + 1, 1);
f[1] = 1;
int id = 0;
do {
++id;
for (int i = 1; i <= n; ++i) {
pos[p[i]] = i;
}
bool fl = 1;
for (int i = 1; i <= m; ++i) {
fl &= !(p[a[i]] < p[b[i]] && p[c[i]] > p[d[i]]);
}
if (!fl) {
f[id] = 0;
continue;
}
for (int i = 1; i < n; ++i) {
if (pos[i + 1] > pos[i]) {
int t = id + fac[n - pos[i]];
f[t] = (f[t] + f[id]) % Mod;
}
}
} while (next_permutation(p + 1, p + n + 1));
cout << f[id] << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 3 1 2 2 3 1 2 3 4 2 3 3 4
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3 0
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 0
output:
16
result:
ok 1 number(s): "16"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
5 0
output:
768
result:
ok 1 number(s): "768"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
6 0
output:
292864
result:
ok 1 number(s): "292864"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
8 0
output:
285163978
result:
ok 1 number(s): "285163978"
Test #8:
score: 0
Accepted
time: 10ms
memory: 5132kb
input:
9 0
output:
67080514
result:
ok 1 number(s): "67080514"
Test #9:
score: 0
Accepted
time: 78ms
memory: 17808kb
input:
10 8 1 2 2 3 1 2 3 4 1 2 4 5 1 2 5 6 1 2 6 7 1 2 7 8 1 2 8 9 1 2 9 10
output:
869798492
result:
ok 1 number(s): "869798492"
Test #10:
score: 0
Accepted
time: 68ms
memory: 17708kb
input:
10 10 1 3 2 4 2 4 3 5 3 5 1 5 1 2 4 5 5 6 6 7 5 7 4 6 1 3 3 5 3 5 1 3 6 7 7 8 7 8 8 9
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
3 2 1 2 1 3 2 3 1 3
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 4 1 2 2 3 1 2 2 3 1 2 2 3 1 2 2 3
output:
8
result:
ok 1 number(s): "8"
Test #13:
score: 0
Accepted
time: 72ms
memory: 17848kb
input:
10 10 1 3 3 5 2 6 6 8 1 5 7 8 2 7 5 7 4 5 9 10 8 10 5 8 1 6 2 6 1 6 2 8 3 5 9 10 3 6 5 7
output:
772654158
result:
ok 1 number(s): "772654158"
Test #14:
score: 0
Accepted
time: 73ms
memory: 17836kb
input:
10 10 1 2 3 4 2 5 6 7 1 4 7 8 2 6 5 6 4 5 9 10 8 9 5 7 1 5 1 3 1 5 4 5 3 4 9 10 1 2 2 3
output:
298701136
result:
ok 1 number(s): "298701136"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
7 0
output:
102498303
result:
ok 1 number(s): "102498303"
Test #16:
score: 0
Accepted
time: 95ms
memory: 17764kb
input:
10 0
output:
411322526
result:
ok 1 number(s): "411322526"