QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267818#7302. Walk of Length 6Mine_KingWA 240ms3992kbC++142.9kb2023-11-27 19:04:502023-11-27 19:04:51

Judging History

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

  • [2023-11-27 19:04:51]
  • 评测
  • 测评结果:WA
  • 用时:240ms
  • 内存:3992kb
  • [2023-11-27 19:04:50]
  • 提交

answer

// 願ったんなら叶えてしまえやって
// Think twice, code once.
#include <bitset>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n;
unsigned ans;
bitset<1005> g[1005];

unsigned calc1() { //
	unsigned res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) res += g[i][j];
	return res;
}
unsigned calc2() { //
	unsigned res = 0;
	for (int i = 1; i <= n; i++) {
		int num = g[i].count();
		res += num * (num - 1) / 2;
	}
	return res;
}
unsigned calc3() {
	unsigned res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (g[i][j]) {
				int A = g[i].count() - 1, B = g[j].count() - 1, C = (g[i] & g[j]).count();
				A -= C, B -= C;
				// eprintf("%d %d %d %d %d\n", i, j, A, B, C);
				if (A >= 0 && B >= 0)
					res += A * B + A * C + B * C;
				if (C >= 0) res += C * (C - 1);
			}
	return res;
}
unsigned calc4() {
	long long res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (g[i][j]) res += (g[i] & g[j]).count();
	return res / 3;
}
unsigned calc5() { //
	unsigned res = 0;
	for (int i = 1; i <= n; i++) {
		int num = g[i].count();
		if (num >= 3) res += (long long)num * (num - 1) * (num - 2) / 6;
	}
	return res;
}
unsigned calc6() {
	unsigned res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			if (g[i][j]) {
				int num = (g[i] & g[j]).count();
				res += num * (num - 1) / 2;
			}
	return res;
}
unsigned calc7() {
	long long res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++) {
			int num = (g[i] & g[j]).count();
			res += num * (num - 1) / 2;
		}
	return res / 2;
}
unsigned calc8() {
	unsigned res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j) {
				int A = (g[i] & g[j]).count(), B = g[i].count() - 2 - g[i][j];
				if (B > 0) res += (long long)A * (A - 1) / 2 * B;
			}
	return res;
}
unsigned calc9() {
	unsigned res = 0;
	for (int i = 1; i <= n; i++) {
		unsigned num = 0;
		for (int j = 1; j <= n; j++)
			if (g[i][j]) num += (g[i] & g[j]).count();
		num /= 2;
		if (num > 1) res += num * (num - 1) / 2;
	}
	return res - calc6() * 2;
}

int main() {
	while (scanf("%d", &n) != EOF) {
		for (int i = 1; i <= n; i++) {
			g[i].reset();
			for (int j = 1; j <= n; j++) {
				int x;
				scanf("%1d", &x);
				g[i][j] = x;
			}
		}
		ans = 0;
		ans += calc1() * 2, ans += calc2() * 12, ans += calc3() * 6;
		ans += calc4() * 24, ans += calc5() * 12, ans += calc6() * 36;
		ans += calc7() * 48, ans += calc8() * 12, ans += calc9() * 24;
		// eprintf("%d\n", calc8());
		printf("%u\n", ans);
	}
	return 0;
}
/*
6
011111
101111
110111
111011
111101
111110
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
011
101
110
4
0101
1010
0101
1010
6
011111
101111
110111
111011
111101
111110

output:

66
128
14910

result:

ok 3 number(s): "66 128 14910"

Test #2:

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

input:

1
0
2
01
10
3
011
100
100
3
011
101
110
4
0001
0001
0001
1110
4
0101
1001
0001
1110
4
0100
1001
0001
0110
4
0101
1011
0101
1110
4
0110
1001
1001
0110
4
0111
1011
1101
1110
5
01000
10111
01000
01000
01000
5
01111
10001
10000
10000
11000
5
01100
10110
11011
01100
00100
5
01111
10110
11010
11100
10000
...

output:

0
2
16
66
54
116
36
298
128
732
128
202
408
878
80
172
794
1372
56
372
668
190
2370
142
300
300
100
650
1216
432
4100
250
336
566
1072
988
1602
850
2648
446
1434
4438
160
264
524
1030
130
802
258
362
1380
518
1650
2372
3538
5460
488
106
234
892
1542
482
362
790
1326
2186
288
1176
1784
808
5232
7358
...

result:

ok 143 numbers

Test #3:

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

input:

20
01110111111111111111
10111111111011111111
11011111101111101111
11101110111011111111
01110111111011011011
11111011101111011110
11111101111111101111
11101110111111111111
11111111011111111111
11011011101111101111
11111111110111010111
10100111111011111111
11111111111101111110
11111111111110111111
111...

output:

11368772
12823048
16678042
17149212
18099376
18616410
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
19138700
191...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 14ms
memory: 3780kb

input:

50
01111111111101010111111110111111111111001110111111
10111111011010111101111111011111111111111111011111
11010101111111111110011110001111111111111111111111
11101111110101111110101111111111111111111101111111
11010111111101101111011111111101111111101111111110
111110111011111111111111111111111111111101...

output:

1250940348
1590514050
1984065786
2169894880
2338139630
2348971408
2399983250
2399983250
2389639440
2389639440
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250
2399983250

result:

ok 20 numbers

Test #5:

score: -100
Wrong Answer
time: 240ms
memory: 3992kb

input:

1000
0110000100111110011111111011111111111111111010111011111111110111111111110111110011101111110111111110110111111111111011111100101111000111011011101111110011111101110110111011100111111101101110101111001011011101011101111101111111111111000110011011010111111111111111111010111011011110010111011111101...

output:

1820762090

result:

wrong answer 1st numbers differ - expected: '1943182464425962', found: '1820762090'