QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#114531 | #6641. XOR Dice | willow# | AC ✓ | 52ms | 15164kb | C++14 | 1.5kb | 2023-06-22 14:27:15 | 2023-06-22 14:27:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int n, d, dice[6], r[25], tot, c[maxn], pc[maxn], pr[3];
int main() {
pc[0] = 0;
for(int i = 1; i < maxn; ++ i)
pc[i] = pc[i >> 1] + (i & 1);
scanf("%d%d", &n, &d);
int bit = 0, tmp = d;
while(tmp % 2 == 0)
tmp /= 2, ++ bit;
int now = 0;
for(int j = bit; j < 20; ++ j) {
int x = 1 << j;
r[j] = x % d;
now |= x;
}
for(int j = 1; j < 1 << 20; ++ j) {
if((now & j) != j)
continue;
int all = 0;
for(int k = 0; k < 20; ++ k) {
if(j >> k & 1) {
all += r[k];
}
}
if(all % d == 0) {
c[tot ++] = j;
}
}
for(int s = 0; s < 3; ++ s) {
int cho = -1;
for(int j = 0; j < tot; ++ j) {
if((now & c[j]) != c[j]) {
continue;
}
// cerr << now << " " << c[j] << " " << cho << endl;
if(cho == -1 || pc[cho] > pc[c[j]])
cho = c[j];
}
assert(cho != -1);
pr[s] = cho;
now ^= cho;
}
for(int s = 0; s < 6; ++ s) {
int x = 0;
for(int j = 0; j < 3; ++ j) {
if(s >> j & 1) {
for(int w = 0; w < 20; ++ w) {
if(pr[j] >> w & 1)
x |= 1 << w;
}
}
}
dice[s] = x;
}
for(int i = 0; i < n; ++ i) {
for(int j = 0; j < 6; ++ j)
printf("%d ", dice[j]);
puts("");
}
for(int j = 0; j < 6; ++ j)
for(int k = 0; k < 6; ++ k)
assert((dice[j] ^ dice[k]) % d == 0);
for(int j = 0; j < 6; ++ j)
for(int k = 0; k < 6; ++ k)
for(int l = 0; l < 6; ++ l)
assert((dice[j] ^ dice[k] ^ dice[l]) % d == 0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 28ms
memory: 14776kb
input:
3 2
output:
0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10
result:
ok Correct answer
Test #2:
score: 0
Accepted
time: 17ms
memory: 13720kb
input:
100 60
output:
0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 60 960 1020 15360 15420 0 6...
result:
ok Correct answer
Test #3:
score: 0
Accepted
time: 32ms
memory: 15164kb
input:
99 2
output:
0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 0 2 4 ...
result:
ok Correct answer
Test #4:
score: 0
Accepted
time: 50ms
memory: 11540kb
input:
99 59
output:
0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 4130 6195 8260 10325 0 2065 413...
result:
ok Correct answer
Test #5:
score: 0
Accepted
time: 50ms
memory: 13008kb
input:
93 17
output:
0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 68 85 0 17 34 51 6...
result:
ok Correct answer
Test #6:
score: 0
Accepted
time: 49ms
memory: 12544kb
input:
100 49
output:
0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245 2058 2107 0 49 196 245...
result:
ok Correct answer
Test #7:
score: 0
Accepted
time: 52ms
memory: 13436kb
input:
100 5
output:
0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 80 85 0 5 10 15 8...
result:
ok Correct answer
Test #8:
score: 0
Accepted
time: 50ms
memory: 12776kb
input:
1 57
output:
0 513 1026 1539 2052 2565
result:
ok Correct answer
Test #9:
score: 0
Accepted
time: 25ms
memory: 12384kb
input:
1 22
output:
0 66 132 198 264 330
result:
ok Correct answer
Test #10:
score: 0
Accepted
time: 16ms
memory: 12132kb
input:
1 60
output:
0 60 960 1020 15360 15420
result:
ok Correct answer
Test #11:
score: 0
Accepted
time: 28ms
memory: 14280kb
input:
1 2
output:
0 2 4 6 8 10
result:
ok Correct answer
Test #12:
score: 0
Accepted
time: 5ms
memory: 13088kb
input:
10 24
output:
0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408 0 24 96 120 384 408
result:
ok Correct answer