QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#124977 | #5874. Mystery Square | zhouhuanyi | 0 | 0ms | 0kb | C++11 | 2.6kb | 2023-07-15 21:11:49 | 2023-07-15 21:11:52 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 125
#define M 62
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int T,n,Base,tong[N+1],length,tong2[N+1],length2;
char c[N+1],cs[N+1];
__int128 res,ans,dst;
long long rst;
vector<long long>p[N+1];
int main()
{
bool op;
string s;
T=read();
for (int qt=1;qt<=T;++qt)
{
cin>>s,n=s.length(),length=length2=0,dst=1;
for (int i=1;i<=n;++i) c[i]=cs[i]=s[i-1];
for (int i=n;i>=1;i-=2,dst*=4)
{
op=1;
for (int j=i+1;j<=n;++j)
if (c[j]=='1')
op=0;
if (!op) continue;
Base=(i+1)>>1,length=length2=0;
for (int j=i+1;j<=n;++j) cs[j]='0';
for (int j=1;j<=Base;++j)
if (c[j]=='?')
tong[++length]=j;
for (int j=Base+1;j<=i;++j)
if (c[j]=='?')
tong2[++length2]=j;
if (length<=length2)
{
for (int j=0;j<(1<<length);++j)
{
for (int k=1;k<=length;++k)
{
if (j&(1<<(k-1))) cs[tong[k]]='1';
else cs[tong[k]]='0';
}
res=0;
for (int k=1;k<=i;++k)
{
if (k<=Base) res=(res<<1)|(cs[k]-'0');
else res=(res<<1)|1;
}
rst=0,op=1;
for (int k=M;k>=0;--k)
if ((__int128)(rst+(1ll<<k))*(rst+(1ll<<k))<=res)
rst+=(1ll<<k);
res=(__int128)(rst)*rst,op=1;
for (int k=1;k<=n;++k)
if (cs[k]!='?'&&cs[k]-'0'!=((res>>(n-k))&1))
op=0;
if (op) ans=(__int128)(rst)*rst*dst;
}
}
else
{
for (int j=0;j<(1<<length2);++j)
{
for (int k=1;k<=length2;++k)
{
if (j&(1<<(k-1))) cs[tong2[k]]='1';
else cs[tong2[k]]='0';
}
rst=0;
for (int k=Base+1;k<=n;++k) rst=(rst<<1)|(cs[k]-'0'),p[k].clear();
p[n].push_back(rst&1);
for (int k=n-1;k>=Base+1;--k)
for (int t=0;t<p[j+1].size();++t)
{
if ((((__int128)(p[k+1][t])*p[k+1][t])&((1ll<<(n-k+1))-1))==(rst&((1ll<<(n-k+1))-1))) p[j].push_back(p[j+1][t]);
if ((((__int128)(p[k+1][t]+(1ll<<(n-k)))*(p[j+1][t]+(1ll<<(n-k))))&((1ll<<(n-k+1))-1))==(rst&((1ll<<(n-k+1))-1))) p[j].push_back(p[j+1][t]+(1ll<<(n-k)));
}
for (int k=0;k<p[Base+1].size();++k)
{
res=(__int128)(p[Base+1][k])*p[Base+1][k],op=1;
for (int t=1;t<=n;++t)
if (cs[t]!='?'&&cs[t]-'0'!=((res>>(n-t))&1))
op=0;
if (op) ans=(__int128)(p[Base+1][k])*p[Base+1][k]*dst;
}
}
}
}
printf("Case #%d: ",qt);
for (int i=1;i<=n;++i) printf("%c",(char)(((ans>>(n-i))&1)+'0'));
puts("");
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
25 1??? 1 10??110??00??1000?? 1??010?0110?1010?0?010?0111011?11100?100010?0??0??1 1??11????00??1?1?0?1??01??110110?11?00100110?00100?0?00 11?1?1???11111?11?1??11110000?00?????00??0?000?000?1 10??000000?0?00000?00000000??0?0000???00??????0000??? 101???11??11000?????1??1?1??10??0?0100011?0001?01011001...
output:
Case #1: 1001 Case #2: 1 Case #3: 1011110110000100001 Case #4: 111010001100101000001010111011011100110001000110001
result:
Subtask #2:
score: 0
Runtime Error
Test #2:
score: 0
Runtime Error
input:
25 1????????????????????111101010000011100110101111000001011111100110000011000101100000010010110100101000???????????????????? 10?11100?000111??11?01010110100??1?100111?001000000??0101?110?0111?011?11?1??00010111?010??100?100??10?010?001001110111110?1 1000100111100100110011010111100001111010?????????...