QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#427867#8769. Champernowne Substringucup-team3586#WA 1086ms7452kbC++234.3kb2024-06-01 16:14:422024-06-01 16:14:44

Judging History

你现在查看的是最新测评结果

  • [2024-06-01 16:14:44]
  • 评测
  • 测评结果:WA
  • 用时:1086ms
  • 内存:7452kb
  • [2024-06-01 16:14:42]
  • 提交

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'