QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #500841 | #1263. Keep It Cool | MnZn | AC ✓ | 88ms | 22756kb | C++14 | 1.2kb | 2024-08-01 21:37:31 | 2024-08-01 21:37:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5, mod = 998244353;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef vector<int> vi;
// #define ALL(x) x.begin(), x.end()
#define ALL(x, l, r) &x[l], &x[r] + 1
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for (int i = (a); i >= (b); --i)
template <typename T>
inline void chkmx(T &a, T b) { (a < b) && (a = b); }
template <typename T>
inline void chkmn(T &a, T b) { (a > b) && (a = b); }
int n, m, cnt, p[N], f[N], v[N], fc[15];
tuple<int, int, int, int> g[N];
void Add(int &x, int y){
x += y, (x >= mod) && (x -= mod);
}
void Sol(int x){
For(i, 1, n) v[p[i]] = i;
For(i, 1, m){
auto [a, b, c, d] = g[i];
if(p[a] < p[b] && p[c] > p[d])
return ;
}
For(i, 1, n - 1) if(v[i] < v[i + 1])
Add(f[x + fc[n - v[i]]], f[x]);
}
signed main() {
cin >> n >> m;
fc[0] = 1;
For(i, 1, n) fc[i] = fc[i-1] * i;
For(i, 1, n) p[i] = i;
For(i, 1, m) {
auto &[a, b, c, d] = g[i];
cin >> a >> b >> c >> d;
}
f[1] = 1;
do{ Sol(++ cnt); }while(next_permutation(ALL(p, 1, n)));
cout << f[cnt];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9684kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9816kb
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: 1ms
memory: 9772kb
input:
3 0
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9684kb
input:
4 0
output:
16
result:
ok 1 number(s): "16"
Test #5:
score: 0
Accepted
time: 1ms
memory: 9684kb
input:
5 0
output:
768
result:
ok 1 number(s): "768"
Test #6:
score: 0
Accepted
time: 1ms
memory: 9752kb
input:
6 0
output:
292864
result:
ok 1 number(s): "292864"
Test #7:
score: 0
Accepted
time: 0ms
memory: 9740kb
input:
8 0
output:
285163978
result:
ok 1 number(s): "285163978"
Test #8:
score: 0
Accepted
time: 9ms
memory: 9684kb
input:
9 0
output:
67080514
result:
ok 1 number(s): "67080514"
Test #9:
score: 0
Accepted
time: 65ms
memory: 16736kb
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: 47ms
memory: 15712kb
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: 1ms
memory: 9688kb
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: 9756kb
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: 46ms
memory: 21800kb
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: 55ms
memory: 17632kb
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: 9744kb
input:
7 0
output:
102498303
result:
ok 1 number(s): "102498303"
Test #16:
score: 0
Accepted
time: 88ms
memory: 22756kb
input:
10 0
output:
411322526
result:
ok 1 number(s): "411322526"