QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #417452 | #1263. Keep It Cool | Harry27182 | AC ✓ | 135ms | 17916kb | C++14 | 739b | 2024-05-22 18:55:55 | 2024-05-22 18:55:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,fac[15],p[15],a[15],b[15],c[15],d[15],val[15],dp[5000005];
const int mod=998244353;
void Add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
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];
int cur=1;fac[0]=1;dp[1]=1;
for(int i=1;i<=n;i++)p[i]=i,fac[i]=fac[i-1]*i;
do
{
int flag=1;
for(int i=1;i<=m;i++)
{
if(p[a[i]]<p[b[i]]&&p[c[i]]>p[d[i]]){flag=0;break;}
}
if(flag==0)dp[cur]=0;
for(int i=1;i<=n;i++)val[p[i]]=i;
for(int i=1;i<n;i++)
{
if(val[i]<val[i+1])Add(dp[cur+fac[n-val[i]]],dp[cur]);
}
cur++;
}while(next_permutation(p+1,p+n+1));
cout<<dp[fac[n]];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
2 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
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: 3696kb
input:
3 0
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 0
output:
16
result:
ok 1 number(s): "16"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
5 0
output:
768
result:
ok 1 number(s): "768"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
6 0
output:
292864
result:
ok 1 number(s): "292864"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
8 0
output:
285163978
result:
ok 1 number(s): "285163978"
Test #8:
score: 0
Accepted
time: 3ms
memory: 5108kb
input:
9 0
output:
67080514
result:
ok 1 number(s): "67080514"
Test #9:
score: 0
Accepted
time: 94ms
memory: 17912kb
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: 109ms
memory: 17900kb
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: 3604kb
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: 3676kb
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: 135ms
memory: 17796kb
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: 125ms
memory: 17792kb
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: 3640kb
input:
7 0
output:
102498303
result:
ok 1 number(s): "102498303"
Test #16:
score: 0
Accepted
time: 85ms
memory: 17916kb
input:
10 0
output:
411322526
result:
ok 1 number(s): "411322526"