QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #302076 | #7789. Outro: True Love Waits | zzuqy# | WA | 170ms | 13652kb | C++14 | 2.0kb | 2024-01-10 16:01:18 | 2024-01-10 16:01:20 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define N 1000009
#define mod 1000000007
using namespace std;
int qpow(int mt, int p) {
int ret = 1;
for (; p; mt = mt * mt % mod, p >>= 1)
if (p & 1)
ret = ret * mt % mod;
return ret;
}
int F(int x) {
return (qpow(4, x) + mod - 4) * qpow(3, mod - 2) % mod;
}
char a[N], b[N];
int k;
int f[N];
int calc(char x, char y) {
if (x == '0' && y == '0')
return 0;
if (x == '1' && y == '0')
return 1;
if (x == '1' && y == '1')
return 2;
if (x == '0' && y == '1')
return 3;
return 114514;
}
int lena, lenb;
int solve() {
scanf("%s%s%lld", a, b, &k);
lena = strlen(a), lenb = strlen(b);
a[lena] = '0';
b[lenb] = '0';
for (int i = 0; i < lena / 2; i++)
swap(a[i], a[lena - 1 - i]);
for (int i = 0; i < lenb / 2; i++)
swap(b[i], b[lenb - 1 - i]);
lena = max(lena, lenb);
for (int i = 0; i < lena; i++)
if (b[i] == '1') {
if (a[i] == '0')
a[i] = '1';
else if (a[i] == '1')
a[i] = '0';
}
while (lena >= 1 && a[lena - 1] == '0')
lena--;
if (lena == 0)
return F(k);
if (lena <= 2)
return k >= 2 ? -1 : calc(a[0], a[1]);
bool flag = 1;
for (int i = 0; i + 2 < lena; i += 2)
if (a[i] == '1' || a[i + 1] == '1')
flag = 0;
if (flag == 1) {
if (k >= 3)
return -1;
else {
int ans = calc(a[(lena - 1) / 2 * 2],
a[(lena - 1) / 2 * 2 + 1]) * (f[(lena - 1) / 2 + 1] + 1) + (k == 2) * f[(lena - 1) / 2 + 1 ];
return ans % mod;
}
} else {
if (k >= 2)
return -1;
int ans = 0;
for (int i = (lena - 1) / 2 * 2; i >= 0; i -= 2) {
ans = (ans + (f[i / 2 + 1 ] + 1) * calc(a[i], a[i + 1])) % mod;
}
return ans;
}
return 114514;
}
signed main() {
fill(a, a + N, '0');
fill(b, b + N, '0');
for (int i = 1; i < N; i++)
f[i] = F(i);
int t;
scanf("%lld", &t);
while (t--) {
printf("%lld\n", solve());
for (int i = 0; i < lena; i++)
a[i] = b[i] = '0';
}
}
/*
5
1 10 1
1 10 2
100 0 2
11 11 3
1111 0 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 170ms
memory: 13632kb
input:
4 1 10 1 1 10 2 100 0 2 11 11 3
output:
2 -1 9 20
result:
ok 4 number(s): "2 -1 9 20"
Test #2:
score: 0
Accepted
time: 166ms
memory: 13576kb
input:
1 0 0 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 166ms
memory: 13652kb
input:
100 110111 11111 1 10110 101101 1 11010 111111 1 100110 1 1 10010 11010 1 1100 10111 1 100100 111110 1 101110 101100 1 1011 10110 1 110100 1110 1 11010 11000 1 11110 1000 1 111000 11101 1 110 1001 1 101010 11000 1 10 111110 1 110001 101000 1 1010 1000 1 10101 11 1 111011 11010 1 110001 100000 1 1100...
output:
78 59 69 70 15 38 39 3 32 60 3 29 69 12 45 52 37 3 34 64 22 39 54 69 65 27 33 76 34 18 57 13 81 15 23 70 69 36 18 2 29 42 69 54 6 0 63 3 29 15 10 16 80 24 37 59 71 13 23 31 21 34 23 48 21 47 7 44 42 3 37 75 59 29 55 39 29 28 29 70 55 16 54 47 24 18 79 60 8 26 64 58 32 6 8 37 2 68 42 44
result:
wrong answer 19th numbers differ - expected: '29', found: '34'