QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #750509 | #8769. Champernowne Substring | ydzr00000 | WA | 22ms | 3936kb | C++17 | 7.1kb | 2024-11-15 14:46:39 | 2024-11-15 14:46:41 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
string pattern="";
const int mod=998244353;
__int128 pw10[29],pref[29];
template<typename T>
inline string ToString(T x)
{
if(!x)
return "0";
string t="";
while(x)
{
t+=(char)(x%10+'0');
x/=10;
}
reverse(t.begin(),t.end());
return t;
}
inline __int128 ToInteger(string x)
{
__int128 num=0;
int l=x.length(),p=0;
for(int i=p;i<l;i++)
num=(num<<1)+(num<<3)+(x[i]^48);
return num;
}
inline __int128 calc(__int128 val)
{
int dig=0;
for(int i=0;i<=27;i++)
if(pw10[i]<=val)
dig=i;
return pref[dig]+(dig+1)*(val-pw10[dig])+1;
}
inline void solve()
{
string s;
cin>>s;
int n=s.length(),m=pattern.length();
__int128 ans=1e36;
//BruteForce Matching
for(int i=0;i<=m-n;i++)
{
bool match=true;
for(int j=0;j<n;j++)
if(s[j]!='?')
match&=(s[j]==pattern[i+j]);
if(match)
{
ans=i+1;
break;
}
}
//Crossing 10-power number
for(int t=5;t<=27;t++)
{
auto x=pw10[t];
string npattern="";
int c=0;
for(auto i=x-6;i<=x+6;i++)
{
if(i==x)
c=npattern.length();
npattern+=ToString(i);
}
int l=npattern.size();
for(int i=0;i<=l-n;i++)
{
bool match=true;
for(int j=0;j<n;j++)
if(s[j]!='?')
match&=(s[j]==npattern[i+j]);
if(match)
{
ans=min(ans,pref[t]+(i-c)+1);
break;
}
}
}
//Only One Number
string u=s;
int more=0;
if(u[0]=='0')
u='1'+u,more=1;
else if(u[0]=='?')
u[0]='1';
for(auto &ch: u)
if(ch=='?')
ch='0';
__int128 val=ToInteger(u);
ans=min(ans,calc(val)+more);
//At Least 2 Numbers
for(int st=0;st<n;st++)
for(int len=5,ed=st+len-1;len<=n;len++,ed++)
{
vector<int>val[len];
string w=s,v=w;
while(w.size()<=ed)
w.push_back('?');
for(int i=0;i<=max(n-1,ed);i++)
val[((i-st)%len+len)%len].push_back(i);
auto completeHigh=[&](const int &up)->bool
{
for(int i=0;i<=up;i++)
{
int dig=(!i);
int prep=-1;
for(auto pos: val[i])
if(v[pos]!='?')
prep=(v[pos]-'0');
if(!i&&!prep)
return false;
if(prep==-1)
prep=dig;
bool flg=true;
for(auto pos: val[i])
{
if(v[pos]=='?')
v[pos]=(char)(prep+'0');
else
flg&=(v[pos]-'0'==prep);
}
if(!flg)
return false;
}
return true;
};
auto completeLow=[&](bool carry)->bool
{
int sp=ed,sv=9;
bool already=false;
for(auto pos: val[len-1])
if(v[pos]!='?')
sp=pos,sv=v[pos]-'0',already=true;
while(sp>=len)
sp-=len,sv--;
if(sv<0&&!carry)
return false;
if(!already)
sv=0;
bool flg=true;
for(auto pos: val[len-1])
{
if(v[pos]=='?')
v[pos]=(char)(((sv+10)%10)+'0');
else
flg&=(v[pos]-'0'==((sv+10)%10));
sv++;
}
if(sv>=10)
return false;
return flg;
};
//If no carry
v=w;
if(completeHigh(len-2)&&completeLow(0))
{
__int128 val=ToInteger(v.substr(st,len));
ans=min(ans,calc(val)-st);
}
//If carry
v=w;
if(v[ed]!='0'&&v[ed]!='?')
continue;
for(int carry=2;carry<=len;carry++)
{
v=w;v[ed]='0';
if(!completeLow(1))
continue;
if(len>carry&&!completeHigh(len-carry-1))
continue;
bool flg=true;
for(int d=1;d<carry-1;d++)
{
int pos=ed-d;
while(pos<=max(ed,n-1))
{
flg&=(v[pos]=='0'||v[pos]=='?');
v[pos]='0';
pos+=len;
}
pos=ed-d-len;
while(pos>=0)
{
flg&=(v[pos]=='9'||v[pos]=='?');
v[pos]='9';
pos-=len;
}
}
if(!flg)
continue;
int pos=ed-(carry-1);
int sp=-1,ss=-1;
while(pos<=max(ed,n-1))
{
if(v[pos]!='?')
ss=(v[pos]-'0');
pos+=len;
}
pos=ed-(carry-1)-len;
while(pos>=0)
{
if(v[pos]!='?')
sp=(v[pos]-'0');
pos-=len;
}
if(sp!=-1&&ss!=-1&&ss!=sp+1)
continue;
if(sp!=-1)
ss=sp+1;
else if(ss!=-1)
sp=ss-1;
else
sp=0,ss=1;
if(sp<0||ss>=10)
continue;
pos=ed-(carry-1);
while(pos<=max(ed,n-1))
{
flg&=(v[pos]-'0'==ss||v[pos]=='?');
v[pos]=(ss+'0');
pos+=len;
}
pos=ed-(carry-1)-len;
while(pos>=0)
{
flg&=(v[pos]-'0'==sp||v[pos]=='?');
v[pos]=(sp+'0');
pos-=len;
}
if(!flg)
continue;
__int128 val=ToInteger(v.substr(st,len));
ans=min(ans,calc(val)-st);
}
}
long long result=ans%mod;
printf("%lld\n",result);
}
int main(){
for(int i=1;i<=15000;i++)
pattern+=ToString(i);
pw10[0]=1;
for(int i=1;i<=28;i++)
{
pw10[i]=pw10[i-1]*10;
pref[i]=pref[i-1]+(pw10[i]-pw10[i-1])*i;
}
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 3936kb
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: 22ms
memory: 3856kb
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 788888870 488873 902034054 830780534 68888820 5882870
result:
wrong answer 5th lines differ - expected: '902934046', found: '788888870'