QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#279859 | #7789. Outro: True Love Waits | sey_1012 (Boyu Xian, Haoran Song)# | WA | 6ms | 10724kb | C++20 | 1.5kb | 2023-12-09 10:55:44 | 2023-12-09 10:55:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
void chkmin(int &x,int y){x=min(x,y);}
void chkmax(int &x,int y){x=max(x,y);}
const int N=1e6+5,mod=1e9+7;
int read(){
int x=0,f=1; char c=getchar();
while(('0'>c||c>'9')&&c!='-') c=getchar();
if(c=='-') f=0,c=getchar();
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f?x:-x;
}
char s[N],t[N];
int a[N],pow5[N],mp[5];
void solve(){
int k;
scanf("%s%s%d",s+1,t+1,&k);
int n=strlen(s+1),m=strlen(t+1);
for(int i=0; i<n; i++) a[i]^=s[n-i]-'0';
for(int i=0; i<m; i++) a[i]^=t[m-i]-'0';
n=max(n,m)+1; n>>=1;
auto chk = [&](){
for(int i=0; i<n*2; i++) if(a[i]) return;
n=60;
};
chk();
int cur=1,cnt=0,ans=0;
for(int i=0; i<n; i++)
if(a[i*2]==0&&a[i*2+1]==0) cur=min(k,cur*2),cnt++;
else break;
if(cur<k){
for(int i=0; i<=n; i++) a[i*2]=a[i*2+1]=0;
return puts("-1"),void();
}
k--;
for(int i=n-1; ~i; i--){
if(a[i*2]==0&&a[i*2+1]==0){
cnt--; int t=0;
if(cnt<=30&&((k>>cnt)&1)) t=4;
ans=(ans+1ll*t*pow5[i])%mod;
}
else ans=(ans+1ll*mp[a[i*2]+2ll*a[i*2+1]]*pow5[i])%mod;
}
printf("%d\n",ans);
for(int i=0; i<=n; i++) a[i*2]=a[i*2+1]=0;
}
int main(){
mp[1]=1,mp[3]=2,mp[2]=3;
for(int i=pow5[0]=1; i<=1e6; i++) pow5[i]=5ll*pow5[i-1]%mod;
int T=read();
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 10724kb
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: 0ms
memory: 10676kb
input:
1 0 0 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 10192kb
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:
90 67 81 82 15 42 43 3 36 68 3 33 81 12 53 60 41 3 33 76 26 43 62 81 77 31 37 88 38 18 65 13 93 15 27 82 81 40 18 27 33 50 81 62 6 0 75 3 33 15 10 16 92 28 41 67 83 13 27 35 25 38 27 56 25 55 7 52 50 3 41 87 67 33 63 43 33 32 33 82 63 16 62 55 28 18 91 68 8 30 76 66 36 6 8 41 2 80 50 52
result:
wrong answer 1st numbers differ - expected: '78', found: '90'