QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #302062 | #7789. Outro: True Love Waits | zzuqy# | WA | 169ms | 13632kb | C++14 | 2.0kb | 2024-01-10 15:53:09 | 2024-01-10 15:53:09 |
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++)
if (a[i] == '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--) {
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: 166ms
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: 169ms
memory: 13560kb
input:
1 0 0 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 169ms
memory: 13496kb
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:
83 70 72 72 15 49 50 3 45 71 3 46 72 14 61 65 47 3 46 64 37 50 66 72 66 45 45 83 46 19 67 15 87 15 39 72 72 21 19 2 46 42 72 66 9 0 63 3 46 15 10 16 86 40 47 70 73 15 39 44 21 46 39 66 21 65 9 60 42 3 47 82 70 46 67 50 46 45 46 72 67 16 66 65 40 19 84 71 5 44 64 68 45 9 5 47 2 71 42 60
result:
wrong answer 1st numbers differ - expected: '78', found: '83'