QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#427867 | #8769. Champernowne Substring | ucup-team3586# | WA | 1086ms | 7452kb | C++23 | 4.3kb | 2024-06-01 16:14:42 | 2024-06-01 16:14:44 |
Judging History
answer
//泥の分際で私だけの大切を奪おうだなん
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define i128 __int128
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int p=998244353;
int arr[1000003];int len;
i128 prefix[53];
int Arr[53][10003];int Len[53];
int a[53];char s[53];
int val[103];
i128 Func(i128 A)
{
i128 res=0;
for(i128 D=1,N=9; A; ++D,N*=10)
res+=min(A,N)*D,
A-=min(A,N);
return res;
}
void print(i128 i)
{
if(i>9) print(i/10);
putchar(i%10+48);
}
void HaitangSuki()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=1; i<=n; ++i) a[i]=s[i]-48;
for(int i=1; i+n-1<=len; ++i)
{
bool ok=1;
for(int j=0; j<n; ++j)
if(arr[i+j]!=a[j+1]&&s[j+1]!='?'){ok=0;break;}
if(ok){printf("%d\n",i);return;}
}
i128 cur=1e33;
i128 qwq=cur;
for(int D=3; D<=30; ++D)
for(int i=1; i+n-1<=Len[D]; ++i)
{
bool ok=1;
for(int j=0; j<n; ++j)
if(Arr[D][i+j]!=a[j+1]&&s[j+1]!='?'){ok=0;break;}
if(ok){
// printf("trigger %lld\n",(long long)(i+prefix[D]));
cur=min(cur,i+prefix[D]);break;}
}
for(int shift=-1; shift<=40; ++shift)//all position +=shift
{
for(int dig=3; dig<=30; ++dig)
for(int j=1; j<=10; ++j) //last digit
{
i128 first=10-j,target=10;
for(int k=1; k<dig; ++k) //suffix 9s
{
int daobi=0;
for(int l=0; l<dig; ++l)
val[l]=-1;
for(int l=1; l<=n; ++l) if(s[l]!='?')
{
// if(j==4&&dig==7&&k==4&&shift==6)
// {
// printf("%d: ",(int)daobi);
// for(int o=0; o<dig; ++o)
// printf("%d ",val[o]);
// puts("");
// }
int index=(l+shift)/dig;
int pos=(l+shift)%dig;
pos=dig-1-pos;
if(pos<k)
{
i128 temp=first+index;
while(pos--) temp/=10;
if(temp%10!=a[l]) daobi=1;
// if(j==4&&dig==7&&k==4&&shift==6)
// printf("have %d exp %d fnd %d\n",
// int(first+index),int(temp%10),a[l]);
}
else if(pos==k)
{
if(first+index>=target)
{
if(a[l]==0) daobi=2;
if(val[pos]==-1)
val[pos]=a[l]-1;
else if(val[pos]!=a[l]-1)
daobi=3;
}
else
{
if(val[pos]==-1)
val[pos]=a[l];
else if(val[pos]!=a[l])
daobi=4;
}
}
else
{
if(val[pos]==-1)
val[pos]=a[l];
else if(val[pos]!=a[l])
daobi=5;
}
}
else
{
int index=(l+shift)/dig;
int pos=(l+shift)%dig;
pos=dig-1-pos;
if(pos<k)
{
}
else if(pos==k)
{
if(first+index>=target)
{
if(val[pos]==9) daobi=2;
}
else
{
}
}
else
{
}
}
if(val[dig-1]==0) daobi=1;
// if(k>1&&val[k]==9) daobi=1;
if(daobi){first+=target*9;
target*=10;continue;}
for(int i=dig-1; i>=k; --i)
if(val[i]==-1) val[i]=(i==dig-1);
i128 prefix=0;
for(int i=dig-1; i>=k; --i)
prefix=prefix*10+val[i];
prefix=prefix*target+first;
// if(prefix<=1e)
// printf("%d %d %lld\n",dig,shift,(long long)prefix);
--prefix;
// if(dig<=7){
// printf("!");
// print(prefix),puts("");
// }
cur=min(cur,Func(prefix)+shift+2);
first+=target*9;
target*=10;
// assert(first==target-j);
}
}
}
assert(qwq!=cur);
int ans=cur%998244353;
printf("%d\n",ans);
return ;
}
signed main()
{
for(int i=1; i<=110000; ++i)
{
int o[13];int top=0;
for(int x=i; x; x/=10) o[++top]=x%10;
while(top) arr[++len]=o[top--];
}
int dig=3;
for(i128 I=1e3; dig<=30; I*=10,++dig)
{
prefix[dig]=Func(I-9);
for(i128 i=I-8; i<=I+8; ++i)
{
int o[103];int top=0;
for(i128 x=i; x; x/=10) o[++top]=x%10;
while(top) Arr[dig][++Len[dig]]=o[top--];
}
}
for(int T=read();T--;) HaitangSuki();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 132ms
memory: 7452kb
input:
9 0 ???1 121 1?1?1 ??5?54?50?5?505?65?5 000000000000 ?2222222 ?3????????9??8???????1??0 9?9??0????????????2
output:
11 7 14 10 314159 796889014 7777 8058869 38886
result:
ok 9 lines
Test #2:
score: -100
Wrong Answer
time: 1086ms
memory: 7220kb
input:
10 0000000000000000000000000 0000000?002100000000000?0 6999?999?999999989?999999 0???0?1000?0??000?????0?1 9??9?999998?9?999999100?0 96?9997999?8999991????010 99?99??999999999??????99? ?0?0000?00000000?0210?0?0 99?999?999?99?9??999?9?9? 9?????9?99?99??9??99??9??
output:
545305036 574985081 788888865 5889591 902934046 488873 902034054 830780534 68888820 38880
result:
wrong answer 10th lines differ - expected: '5882870', found: '38880'