QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#639940 | #7789. Outro: True Love Waits | D06 | WA | 1ms | 4648kb | C++14 | 2.0kb | 2024-10-14 00:15:28 | 2024-10-14 00:15:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
string s,t;
bitset<1000000>m,tmp;
int step(bitset<1000000>x)
{
int id=x._Find_first();
return id/2+1;
}
long long power(int n,int p)
{
if(p==0)
{
return 1;
}
long long tmp=power(n,p/2);
if(p%2==1)
{
return tmp*tmp%mod*n%mod;
}
return tmp*tmp%mod;
}
int calc(int k)
{
return (power(4,k)-1)*power(3,1000000005)%mod;
}
void shuchu(bitset<1000000>x)
{
bitset<10>w=x.to_ulong();
cout<<w<<endl;
}
int ask(int len,int k)
{
// shuchu(m);
// cout<<len<<" "<<k<<endl;
if(len<m._Find_first()+1)
{
return 1;
}
if(!m[len-1])
{
return ask(len-1,k);
}
if(len==m._Find_first()+1&&step(m)==k)
{
return (calc(len/2+1)*power(2,len%2)-(len%2==0))%mod;
}
else if(len==m._Find_first()+1)
{
if(k==1)
{
return (calc((len-1)/2+1)*power(2,(len-1)%2)-((len-1)%2==0))%mod*power(2,1000000005)%mod*3%mod+1;
}
tmp=m;
// cout<<len-2*(step(m)-k+1)-(len%2==0)<<" "<<step(m)<<" "<<len<<" "<<k<<endl;
tmp.set(len-2*(step(m)-k+1)-(len%2==0),1);
m=tmp;
return ask(len,k-1)+1;
}
else
{
if(len%2==0)
{
if(m[len-1-1])
{
tmp.reset();
tmp.set(len-1-1,1);
m=m^tmp;
return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2))%mod;
}
else
{
// cout<<calc((len-1)/2+1)*power(2,(len-1)%2)*power(2,1000000005)%mod*3%mod<<endl;
return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2)*power(2,1000000005)%mod*3%mod)%mod;
}
}
// cout<<calc((len-1)/2+1)*power(2,(len-1)%2)<<endl;
return (ask(len-1,k)+calc((len-1)/2+1)*power(2,(len-1)%2))%mod;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
int k;
cin>>s>>t>>k;
m=bitset<1000000>(s)^bitset<1000000>(t);
if(m.none())
{
cout<<calc(k)-1<<"\n";
}
else if(k>step(m))
{
cout<<-1<<"\n";
}
else
{
cout<<ask(max(s.size(),t.size()),k)-1<<"\n";
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4416kb
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: 1ms
memory: 4340kb
input:
1 0 0 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 4648kb
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 29 64 22 39 54 69 65 27 33 76 34 18 57 13 81 15 23 70 69 36 18 23 29 42 69 54 6 0 63 3 29 15 10 16 80 24 37 59 71 13 23 31 30 34 23 48 30 48 7 44 42 3 37 75 59 29 55 39 29 28 29 70 55 16 54 48 24 18 79 60 8 27 64 58 32 6 8 37 2 69 42 44
result:
wrong answer 61st numbers differ - expected: '21', found: '30'