QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107210#3915. Sort hackingDeterminantAC ✓53ms4060kbC++14512b2023-05-20 16:00:432023-05-20 16:00:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 16:00:47]
  • 评测
  • 测评结果:AC
  • 用时:53ms
  • 内存:4060kb
  • [2023-05-20 16:00:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;int n,m,a[207],b[207],c[17];long long s=1,f[32769];
int main(){
	scanf("%d%d",&n,&m);for(int i=1;i<=m;++i)scanf("%d%d",&a[i],&b[i]);f[0]=1;
	for(int i=1;i<=n;++i)s*=i;
	for(int i=0;i<(1<<n);++i)for(int j=1;j<=n;++j)if(!((i>>(j-1))&1)){
		int fl=1;for(int k=1;k<=n;++k){if((i>>(k-1))&1)++fl,c[k]=0;else c[k]=2;}
		c[j]=1;for(int k=1;k<=m;++k)if(c[a[k]]>c[b[k]])swap(c[a[k]],c[b[k]]);
		if(c[fl]==1)f[i|(1<<(j-1))]+=f[i];
	}
	printf("%lld\n",s-f[(1<<n)-1]);
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3644kb

input:

3 3
1 2
2 3
1 3

output:

2

result:

ok answer is '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

2 1
1 2

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

2 1
2 1

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

3 2
2 3
1 3

output:

4

result:

ok answer is '4'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

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

output:

0

result:

ok answer is '0'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

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

output:

12

result:

ok answer is '12'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

4 4
2 1
3 4
1 3
2 4

output:

20

result:

ok answer is '20'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

4 3
2 1
3 4
1 3

output:

20

result:

ok answer is '20'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

5 9
2 1
4 5
3 5
3 4
1 5
1 3
2 4
1 2
3 4

output:

0

result:

ok answer is '0'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

5 8
2 1
4 5
3 5
3 4
1 5
1 3
2 4
1 2

output:

72

result:

ok answer is '72'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

5 7
2 1
4 5
3 5
3 4
1 5
1 3
2 4

output:

96

result:

ok answer is '96'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

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

output:

360

result:

ok answer is '360'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

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

output:

720

result:

ok answer is '720'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

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

output:

0

result:

ok answer is '0'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

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

output:

20160

result:

ok answer is '20160'

Test #16:

score: 0
Accepted
time: 26ms
memory: 3828kb

input:

15 69
2 3
1 3
1 2
4 5
7 6
6 4
7 5
5 4
7 6
5 1
6 2
7 3
3 1
4 2
2 1
4 3
7 5
6 5
8 9
11 10
10 8
11 9
9 8
11 10
13 12
14 15
12 14
13 15
12 13
14 15
8 12
9 13
10 14
11 15
8 10
9 11
8 9
10 11
12 14
13 15
12 13
14 15
1 9
2 10
3 11
4 12
5 13
6 14
7 15
1 5
2 6
3 7
4 8
1 3
2 4
1 2
3 4
5 7
6 8
5 6
7 8
9 13
10 ...

output:

697426329600

result:

ok answer is '697426329600'

Test #17:

score: 0
Accepted
time: 30ms
memory: 3816kb

input:

15 70
2 3
1 3
1 2
4 5
7 6
6 4
7 5
5 4
7 6
5 1
6 2
7 3
3 1
4 2
2 1
4 3
7 5
6 5
8 9
11 10
10 8
11 9
9 8
11 10
13 12
14 15
12 14
13 15
12 13
14 15
8 12
9 13
10 14
11 15
8 10
9 11
8 9
10 11
12 14
13 15
12 13
14 15
1 9
2 10
3 11
4 12
5 13
6 14
7 15
1 5
2 6
3 7
4 8
1 3
2 4
1 2
3 4
5 7
6 8
5 6
7 8
9 13
10 ...

output:

0

result:

ok answer is '0'

Test #18:

score: 0
Accepted
time: 3ms
memory: 3728kb

input:

15 1
2 1

output:

1307674368000

result:

ok answer is '1307674368000'

Test #19:

score: 0
Accepted
time: 49ms
memory: 3828kb

input:

15 105
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 53ms
memory: 3896kb

input:

15 104
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

87178291200

result:

ok answer is '87178291200'

Test #21:

score: 0
Accepted
time: 52ms
memory: 3828kb

input:

15 103
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

174356582400

result:

ok answer is '174356582400'

Test #22:

score: 0
Accepted
time: 45ms
memory: 3784kb

input:

15 102
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

255307852800

result:

ok answer is '255307852800'

Test #23:

score: 0
Accepted
time: 45ms
memory: 4020kb

input:

15 101
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

336259123200

result:

ok answer is '336259123200'

Test #24:

score: 0
Accepted
time: 52ms
memory: 4048kb

input:

15 100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

410983372800

result:

ok answer is '410983372800'

Test #25:

score: 0
Accepted
time: 52ms
memory: 3824kb

input:

15 99
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 6...

output:

479959603200

result:

ok answer is '479959603200'

Test #26:

score: 0
Accepted
time: 48ms
memory: 4052kb

input:

15 104
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 2
2 3
3 4
4 5
5 ...

output:

261273600

result:

ok answer is '261273600'

Test #27:

score: 0
Accepted
time: 37ms
memory: 4060kb

input:

15 105
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
2 1
3 2
4 3
5 4
6 ...

output:

1307674368000

result:

ok answer is '1307674368000'

Test #28:

score: 0
Accepted
time: 52ms
memory: 3892kb

input:

15 200
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
2 1
3 2
4 3
5 4
6 ...

output:

1307674368000

result:

ok answer is '1307674368000'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

1 1
1 1

output:

0

result:

ok answer is '0'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

2 2
1 1
2 2

output:

1

result:

ok answer is '1'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

2 2
2 2
1 1

output:

1

result:

ok answer is '1'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

3 3
1 1
2 2
3 3

output:

5

result:

ok answer is '5'

Test #33:

score: 0
Accepted
time: 4ms
memory: 3892kb

input:

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

output:

1307674367968

result:

ok answer is '1307674367968'

Test #34:

score: 0
Accepted
time: 21ms
memory: 3788kb

input:

15 40
2 3
1 3
1 2
4 5
7 6
6 4
7 5
5 4
7 6
5 1
6 2
7 3
3 1
4 2
2 1
4 3
7 5
6 5
8 9
11 10
10 8
11 9
9 8
11 10
13 12
14 15
12 14
13 15
12 13
14 15
8 12
9 13
10 14
11 15
8 10
9 11
8 9
10 11
12 14
13 15

output:

1307674368000

result:

ok answer is '1307674368000'

Test #35:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

5 9
1 2
2 3
3 4
4 5
1 2
2 3
3 4
2 3
1 2

output:

12

result:

ok answer is '12'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

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

output:

31680

result:

ok answer is '31680'