QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#395476	#7687. Randias Permutation Task	zzuqy^#	WA	238ms	46856kb	C++14	1.6kb	2024-04-21 15:08:07	2024-04-21 15:08:08

Judging History

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

[2024-04-21 15:08:08]
评测

测评结果：WA
用时：238ms
内存：46856kb

查看

[2024-04-21 15:08:07]
提交

answer

#include <bits/stdc++.h>
#define N 189
#define ull unsigned long long
using namespace std;
int n, m;
int a[N][N];
int tmp[N];

void change(int *a, int *b) {

	for (int i = 1; i <= n; i++)
		tmp[i] = a[b[i]];
	for (int i = 1; i <= n; i++)
		a[i] = tmp[i];
}

ull hsh1(int *a) {
	ull ans = 0;
	for (int i = 1; i <= n; i++)
		ans = ans * 1239738 + a[i];
	return ans;
}

ull hsh2(int *a) {
	ull ans = 0;
	for (int i = 1; i <= n; i++)
		ans = ans * 10 + a[i];
	return ans;
}
int b[N][N];
unordered_set<ull>s;

void dfs(int x, int lstx) {
	if (x == m + 1) {
		if (lstx != 0)
			s.insert(hsh1(b[lstx]));
		return;
	}
	dfs(x + 1, lstx);
	for (int i = 1; i <= n; i++) {
		b[x][i] = b[lstx][a[x][i]];
	}
	dfs(x + 1, x);
}
unordered_set<ull>p[N];

int calc(int x, int *c) {
	for (int i = n; i >= 1; i--) {
		b[2][i] = x % 10;
		x /= 10;
	}
	for (int i = 1; i <= n; i++)
		b[1][i] = c[b[2][i]];
	return hsh2(b[1]);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i++)
		b[0][i] = i;
	if (m <= 18) {
		dfs(1, 0);
		cout << s.size() << endl;
	} else if (n <= 9) {
		bool flag = 0;
		p[0].insert(hsh2(b[0]));
		for (int i = 1; i <= m; i++) {
			for (auto c : p[i - 1]) {
				p[i].insert(calc(c, a[i])), p[i].insert(c);
				//cout << calc(c, a[i]) << " " << hsh2(b[0]) << endl;
				if (calc(c, a[i]) == hsh2(b[0]))
					flag = 1;
			}
		}
		cout << p[m].size() - !flag << endl;
	} else
		assert(0);
	return 0;
}
/*
5 4
1 2 3 4 5
5 1 3 4 2
3 4 1 5 2
5 2 4 1 3
2 1
2 1

*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3628kb

input:

output:

result:

ok 1 number(s): "8"

Test #2:

score: 0

Accepted

time: 1ms

memory: 3864kb

input:

2 1
2 1

output:

result:

ok 1 number(s): "1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3788kb

input:

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

180 1
52 71 167 89 165 102 119 125 9 128 180 24 48 172 108 22 164 28 159 111 30 91 67 51 136 97 126 133 177 65 115 157 114 11 171 178 23 127 163 103 99 18 56 94 176 77 44 1 124 74 61 87 4 40 63 92 169 84 146 6 88 55 152 49 10 90 43 174 70 50 69 154 73 147 110 20 82 59 112 12 64 143 16 138 5 170 155 ...

output:

result:

ok 1 number(s): "1"

Test #5:

score: 0

Accepted

time: 1ms

memory: 3708kb

input:

output:

result:

ok 1 number(s): "2"

Test #6:

score: 0

Accepted

time: 1ms

memory: 3564kb

input:

90 2
43 44 28 69 66 18 5 23 87 8 24 89 31 29 81 1 68 2 78 53 49 54 4 13 77 61 33 57 63 85 55 79 46 35 45 64 65 42 30 6 19 74 82 80 17 26 32 59 7 72 16 3 47 73 39 36 25 34 56 86 71 62 84 40 41 11 50 27 20 14 37 12 38 58 48 83 76 70 51 88 22 90 21 9 10 60 15 52 75 67
9 73 52 51 81 16 71 77 6 57 11 75 ...

output:

result:

ok 1 number(s): "3"

Test #7:

score: 0

Accepted

time: 1ms

memory: 3928kb

input:

output:

result:

ok 1 number(s): "6"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3572kb

input:

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

output:

result:

ok 1 number(s): "7"

Test #9:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

output:

result:

ok 1 number(s): "24"

Test #10:

score: 0

Accepted

time: 0ms

memory: 3872kb

input:

45 4
44 38 33 27 25 17 35 4 22 41 15 3 10 16 21 28 23 19 34 37 2 32 43 12 6 31 29 9 45 18 11 30 13 26 42 5 39 40 8 24 14 1 7 20 36
28 43 12 34 21 7 20 26 13 1 25 4 44 32 11 15 33 18 14 5 6 42 45 36 9 35 2 30 38 10 41 27 17 23 19 8 29 16 3 37 40 31 39 22 24
5 22 23 43 36 33 29 39 44 9 35 34 7 42 8 11...

output:

result:

ok 1 number(s): "15"

Test #11:

score: 0

Accepted

time: 1ms

memory: 3624kb

input:

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

output:

result:

ok 1 number(s): "1023"

Test #12:

score: 0

Accepted

time: 45ms

memory: 13772kb

input:

10 18
9 6 4 8 3 7 10 1 2 5
10 9 8 3 5 6 1 2 7 4
8 2 5 4 9 3 1 7 6 10
10 5 2 8 1 6 4 7 9 3
2 3 5 4 10 9 6 8 7 1
6 7 8 10 5 3 4 1 9 2
10 6 4 2 1 5 3 8 9 7
6 8 9 1 2 4 5 3 7 10
7 6 3 1 5 9 2 10 4 8
10 5 7 4 9 1 2 6 3 8
5 4 6 9 3 7 8 1 2 10
5 9 8 2 7 1 3 10 6 4
5 2 10 3 7 1 4 6 9 8
1 10 2 6 5 7 8 9 3 4
...

output:

result:

ok 1 number(s): "252941"

Test #13:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

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

output:

result:

ok 1 number(s): "1023"

Test #14:

score: 0

Accepted

time: 38ms

memory: 13940kb

input:

10 18
8 4 3 10 2 7 9 5 6 1
4 3 5 10 1 7 9 2 8 6
5 8 3 4 10 1 6 9 2 7
3 1 2 4 9 8 7 6 5 10
2 7 3 8 5 10 9 1 6 4
7 9 4 6 3 5 10 1 2 8
5 7 6 8 4 2 10 1 9 3
9 10 3 2 4 6 8 5 1 7
6 5 7 10 2 3 1 4 8 9
7 1 8 2 3 10 6 9 5 4
9 6 1 5 4 8 10 2 7 3
9 5 6 2 10 1 8 3 4 7
1 10 7 4 3 5 9 6 8 2
6 10 4 5 2 9 7 1 8 3
...

output:

result:

ok 1 number(s): "252421"

Test #15:

score: -100

Wrong Answer

time: 238ms

memory: 46856kb

input:

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

output:

result:

wrong answer 1st numbers differ - expected: '342954', found: '343236'