QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267818 | #7302. Walk of Length 6 | Mine_King | WA | 240ms | 3992kb | C++14 | 2.9kb | 2023-11-27 19:04:50 | 2023-11-27 19:04:51 |
Judging History
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'