QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#49397#682. StickersDerekFeng81.818182 434ms6400kbC++2.9kb2022-09-20 21:44:122022-09-20 21:44:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-20 21:44:13]
  • 评测
  • 测评结果:81.818182
  • 用时:434ms
  • 内存:6400kb
  • [2022-09-20 21:44:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
bool comp(vector<int>a,vector<int>b){
	if(a.size()!=b.size())return a.size()<b.size();
	int n=a.size();
	for(int i=n-1;~i;i--)
		if(a[i]!=b[i])return a[i]<b[i];
	return 0;
}
vector<int>I(vector<int>a,vector<int>b){
	vector<int>ans;int jw=0;
	int n=a.size(),m=b.size();
	for(int i=0;i<max(n,m);i++){
		int A=i<n?a[i]:0;
		int B=i<m?b[i]:0;
		ans.push_back((A+B+jw)%10);
		jw=(A+B+jw)/10;
	}if(jw)ans.push_back(jw);
	return ans;
}
vector<int>D(vector<int>a,vector<int>b){
	vector<int>ans;int jw=0;
	int n=a.size(),m=b.size();
	for(int i=0;i<max(n,m);i++){
		int A=i<n?a[i]:0;
		int B=i<m?b[i]:0;
		A-=B+jw,jw=0;
		if(A<0)A+=10,jw=1;
		ans.push_back(A);
	}
	while(!ans.empty()&&ans.back()==0)ans.pop_back();
	return ans;
}
struct BIG{
	vector<int>v;bool fu;
	BIG(){v.clear(),fu=0;}
	void set(int x){
		fu=0,v.clear();if(x<0)fu=1,x=abs(x);
		while(x)v.push_back(x%10),x/=10;
	}
	bool operator <(const BIG o){
		if(fu!=o.fu)return o.fu<fu;
		return comp(v,o.v)^fu;
	}
};
BIG f[104][104],s[104][104];
BIG ans,pw[104],fdp[104],sdp[104];
BIG operator +(BIG a,BIG b){
	BIG ans;
	if(a.fu==b.fu)ans.fu=a.fu,ans.v=I(a.v,b.v);
	else{
		if(a.fu)swap(a,b);
		if(comp(a.v,b.v))ans.fu=1,ans.v=D(b.v,a.v);
		else ans.fu=0,ans.v=D(a.v,b.v);
	}
	return ans;
}
BIG min(BIG a,BIG b){return a<b?a:b;}
void operator +=(BIG &a,const BIG b){a=a+b;}
void write(BIG a){
	if(a.fu)putchar('-');
	reverse(a.v.begin(),a.v.end());
	for(int i=0;i<a.v.size();i++)putchar(a.v[i]+'0');
}
int a[10];
int main(){
	for(int i=0;i<10;i++)scanf("%d",&a[i]);
	for(int i=0;i<100;i++){
		for(int j=0;j<i;j++)pw[i].v.push_back(0);
		pw[i].v.push_back(1);
	}BIG fu1;fu1.set(-1);
	for(int t=0;t<10;t++){
		for(int i=0;i<100;i++){
			f[0][i].set(min(a[t]-i,0));
			s[0][i].set(a[t]-i);
		}
		for(int i=1;i<100;i++){
			fdp[i]=fdp[i-1],sdp[i]=sdp[i-1];
			for(int j=0;i+j<100;j++){
				f[i][j].set(0);s[i][j].set(0);
				for(int c=0;c<10;c++){
					f[i][j]=min(f[i][j],s[i][j]+f[i-1][j+(t==c)]);
					s[i][j]+=s[i-1][j+(t==c)];
				}
			}
			for(int c=1;c<10;c++){
				fdp[i]=min(fdp[i],sdp[i]+f[i-1][t==c]);
				sdp[i]+=s[i-1][t==c];
			}
		}
		int cur=0,D;BIG sum,res;
		if(!t){
			for(int i=1;i<100;i++){
				for(int c=1;c<10;c++){
					if((sum+f[i-1][0]).fu){
						D=i;break;
					}
					sum+=s[i-1][c==t],res+=pw[i-1];
				}
			}
		}else{
			for(int i=99;i;i--){
				if(!fdp[i-1].fu){
					res+=pw[i-1],res+=fu1,sum=sdp[i-1];
					for(int c=1;c<10;c++){
						if((sum+f[i-1][c==t]).fu){
							D=i;cur+=(c==t);
							break;
						}
						sum+=s[i-1][c==t],res+=pw[i-1];
					}
					break;
				}
			}
		}
		for(int i=D-1;i;i--){
			for(int c=0;c<10;c++){
				if((sum+f[i-1][cur+(t==c)]).fu){
					cur+=(t==c);break;
				}
				sum+=s[i-1][cur+(t==c)],res+=pw[i-1];
			}
		}
		if(!t)ans=res;
		else ans=min(ans,res);
	}
	write(ans);
}

詳細信息

Test #1:

score: 9.09091
Accepted
time: 371ms
memory: 6244kb

input:

1 2 1 1 1 1 1 1 1 1

output:

28263827

result:

ok single line: '28263827'

Test #2:

score: 9.09091
Accepted
time: 434ms
memory: 6308kb

input:

1 2 1 1 1 1 1 1 1 1

output:

28263827

result:

ok single line: '28263827'

Test #3:

score: 9.09091
Accepted
time: 383ms
memory: 6400kb

input:

1 2 2 2 2 1 1 1 1 1

output:

5555555554

result:

ok single line: '5555555554'

Test #4:

score: 9.09091
Accepted
time: 386ms
memory: 6244kb

input:

2 2 2 2 2 2 2 2 2 2

output:

1999919999999980

result:

ok single line: '1999919999999980'

Test #5:

score: 9.09091
Accepted
time: 384ms
memory: 6168kb

input:

4 3 2 2 2 2 2 2 2 3

output:

282638284722222221

result:

ok single line: '282638284722222221'

Test #6:

score: 0
Wrong Answer
time: 401ms
memory: 6372kb

input:

2 4 3 3 3 3 3 3 3 3

output:

1000138075973881055977

result:

wrong answer 1st lines differ - expected: '1005594043670359641774', found: '1000138075973881055977'

Test #7:

score: 9.09091
Accepted
time: 376ms
memory: 6364kb

input:

4 4 4 4 4 4 3 3 3 3

output:

666666666666666666666666666665

result:

ok single line: '666666666666666666666666666665'

Test #8:

score: 0
Wrong Answer
time: 430ms
memory: 6296kb

input:

4 5 5 5 5 5 7 8 9 9

output:

100018440415317236651016706943788849598499

result:

wrong answer 1st lines differ - expected: '100559404367035964177652825361730559404364', found: '100018440415317236651016706943788849598499'

Test #9:

score: 9.09091
Accepted
time: 379ms
memory: 6292kb

input:

6 6 6 6 5 5 5 5 5 5

output:

4999999949999999994999999999499999999949999999953

result:

ok single line: '4999999949999999994999999999499999999949999999953'

Test #10:

score: 9.09091
Accepted
time: 372ms
memory: 6380kb

input:

7 8 8 7 7 7 7 7 7 7

output:

371599993999999999399999999939999999993999999999399999999939999999938

result:

ok single line: '371599993999999999399999999939...3999999999399999999939999999938'

Test #11:

score: 9.09091
Accepted
time: 385ms
memory: 6268kb

input:

9 9 9 9 9 9 9 9 9 9

output:

19999199999999919999999991999999999199999999919999999991999999999199999999919999999918

result:

ok single line: '199991999999999199999999919999...1999999999199999999919999999918'