QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#12500#682. StickersOganesson100 ✓130ms9844kbC++205.4kb2021-08-06 17:09:132022-05-18 03:24:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 03:24:24]
  • 评测
  • 测评结果:100
  • 用时:130ms
  • 内存:9844kb
  • [2021-08-06 17:09:13]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
namespace IO
{
    const int sz=1<<15;
    char inbuf[sz],outbuf[sz];
    char *pinbuf=inbuf+sz;
    char *poutbuf=outbuf;
    inline char _getchar()
    {
        if (pinbuf==inbuf+sz)fread(inbuf,1,sz,stdin),pinbuf=inbuf;
        return *(pinbuf++);
    }
    inline void _putchar(char x)
    {
        if (poutbuf==outbuf+sz)fwrite(outbuf,1,sz,stdout),poutbuf=outbuf;
        *(poutbuf++)=x;
    }
    inline void flush()
    {
        if (poutbuf!=outbuf)fwrite(outbuf,1,poutbuf-outbuf,stdout),poutbuf=outbuf;
    }
}
inline int read(){
	int v=0,f=1;
	char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		v=v*10+c-'0';
		c=getchar();
	}
	return v*f;
}
const int Maxn=155;
const int Bl=100000000;
const int W=8;
struct BigInt{
	int val[20];
	bool neg;
	BigInt(){
		memset(val,0,sizeof(val));
		neg=0;
	}
	BigInt(int v){
		memset(val,0,sizeof(val));
		neg=0;
		val[0]=v;
	}
	void Clear(){
		memset(val,0,sizeof(val));
		neg=0;
	}
	bool operator <(const BigInt &B)const{
		if (neg!=B.neg){
			return neg>B.neg;
		}
		for (int i=19;i>=0;i--){
			if (val[i]!=B.val[i]){
				return neg^(val[i]<B.val[i]);
			}
		}
		return 0;
	}
	void Add(BigInt B){
		if (!neg && !B.neg){
			for (int i=0;i<20;i++){
				val[i]+=B.val[i];
				if (val[i]>=Bl){
					val[i]-=Bl;val[i+1]++;
				}
			}
		}
		else if (!neg && B.neg){
			B.neg^=1;
			if (this->operator<(B)){
				for (int i=0;i<20;i++){
					val[i]=B.val[i]-val[i];
					if (val[i]<0){
						val[i]+=Bl;
						B.val[i+1]--;
					}
				}
				neg^=1;
			}
			else{
				for (int i=0;i<20;i++){
					val[i]-=B.val[i];
					if (val[i]<0){
						val[i]+=Bl;
						val[i+1]--;
					}
				}
			}
		}
		else if (neg && !B.neg){
			neg^=1;
			if (B<(*this)){
				for (int i=0;i<20;i++){
					val[i]-=B.val[i];
					if (val[i]<0){
						val[i]+=Bl;
						val[i+1]--;
					}
				}
				neg^=1;
			}
			else{
				for (int i=0;i<20;i++){
					val[i]=B.val[i]-val[i];
					if (val[i]<0){
						val[i]+=Bl;
						B.val[i+1]--;
					}
				}
			}
		}
		else{
			for (int i=0;i<20;i++){
				val[i]+=B.val[i];
				if (val[i]>=Bl){
					val[i]-=Bl;val[i+1]++;
				}
			}
		}
	}
	void Del(BigInt B){
		bool FZ=1;
		for (int i=0;i<20;i++) FZ&=(B.val[i]==0);
		if (FZ) return;
		B.neg^=1;
		
		Add(B);
	}
	
	void Mul(int k){
		for (int i=19;i>=0;i--){
			val[i]=val[i]*k;
			if(val[i]>=Bl){
				val[i+1]+=val[i]/Bl;
				val[i]%=Bl;
			}
		}
	}
	
	void Out(){
		int p=-1;
		for (int i=19;i>=0;i--){
			if (val[i]){
				p=i;
				break;
			}
		}
		if (p==-1){
			printf("0\n");
			return;
		}
		if (neg){
			putchar('-');
		}
		printf("%d",val[p]);
		for (int i=p-1;i>=0;i--){
			assert(val[i]>=0 && val[i]<Bl);
			printf("%.8d",val[i]);
		}
		printf("\n");
	}
};
BigInt min(BigInt A,BigInt B){
	return (A<B)?A:B;
}
BigInt F[Maxn][Maxn],G[Maxn][Maxn],S[Maxn][Maxn],Ept;
BigInt PW[Maxn];
int a[10],D;
bool bad; 
BigInt Qr(int x,int y,BigInt V,int f=0){
	// first less than V
	if (!(G[x][y]<V)){
		bad=true;
		return BigInt(0);
	}
	if (BigInt(0)<V && f) return BigInt(0);
	if (x==0){
		if (BigInt(0)<V) return BigInt(0);
		else return BigInt(1);
	} 
	BigInt SS,CP;
	for (int i=0;i<10;i++){
		BigInt tmp=SS;
		tmp.Add(G[x-1][y+(i==D)]);
		if (tmp<V && (f||i)){
			V.Del(SS);
			BigInt PS=Qr(x-1,y+(i==D),V,1);
			PS.Add(CP);
			return PS; 
		}
		CP.Add(PW[x-1]);
		SS.Add(S[x-1][y+(i==D)]);
	}
	bad=true;
}
BigInt Get(int d,int A){
	D=d;
	for (int i=0;i<Maxn;i++){
		for (int j=0;j<Maxn;j++){
			F[i][j].Clear();G[i][j].Clear();S[i][j].Clear();
		}
	}
	for (int i=0;i<Maxn;i++){
		S[0][i].val[0]=A-i;
		if (S[0][i].val[0]<0){
			S[0][i].val[0]*=-1;
			S[0][i].neg=1;
		}
		G[0][i]=S[0][i];
		F[0][i].val[0]=1;
	}
	BigInt bas;
	bas.val[0]=1;
	
	for (int i=1;i<Maxn;i++){
		
		for (int j=0;j<Maxn;j++){
			
			if (i+j>=Maxn) continue;
			
			BigInt MnV,Pos,CP,tot;
			MnV.val[19]=11451419;
			for (int k=0;k<10;k++){
				BigInt CS=tot;CS.Add(G[i-1][j+(k==d)]);
				if (CS<MnV){
					MnV=CS;
					Pos=CP;Pos.Add(F[i-1][j+(k==d)]);
				}
				tot.Add(S[i-1][j+(k==d)]);
				CP.Add(bas);
			}
			S[i][j]=tot;
			G[i][j]=MnV;
			F[i][j]=Pos;
		}
		bas.Mul(10);
	}
	//F[5][1].Out();G[5][1].Out();
	if (d){
		for (int i=1;i<Maxn;i++){
			bad=false;
			BigInt tt=Qr(i,0,A,0);
			if (!bad){
				return tt;
			} 
		}
	}
	else{
		BigInt fuck(A);
		fuck.Del(PW[0]);
		for (int i=1;i<Maxn;i++){
			bad=false;
			BigInt tt=Qr(i,0,fuck,0);
			if (!bad){
				return tt;
			} 
			fuck.Del(PW[i]);
		}
		assert(false);
	}
}
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	/*
	int cnt=0;
	for (int i=1;;i++){
		cnt++;
		int j=i;
		while (j){
			if (j%10==4) cnt--;
			j/=10;
		}
		if (cnt<0){
			cerr<<i<<endl;
			return 0;
		}
	}*/
	
	PW[0].val[0]=1;
	for (int i=1;i<Maxn;i++) PW[i]=PW[i-1],PW[i].Mul(10);
	//for (int i=0;i<Maxn;i++) PW[i].Out();
	//return 0;
	for (int i=0;i<10;i++){
		scanf("%d",&a[i]);
		//a[i]=1;
	}
	BigInt Ans;
	Ans.val[19]=11451419;
	for (int i=0;i<10;i++){
		BigInt tmp=Get(i,a[i]);
		//cerr<<i<<endl;
		//tmp.Out();
		if (tmp<Ans){
			Ans=tmp; 
		}
	}
	Ans.Del(BigInt(1));
	Ans.Del(BigInt(1));
	Ans.Out();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 9.09091
Accepted
time: 129ms
memory: 9740kb

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: 121ms
memory: 9828kb

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: 130ms
memory: 9716kb

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: 124ms
memory: 9756kb

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: 123ms
memory: 9844kb

input:

4 3 2 2 2 2 2 2 2 3

output:

282638284722222221

result:

ok single line: '282638284722222221'

Test #6:

score: 9.09091
Accepted
time: 125ms
memory: 9724kb

input:

2 4 3 3 3 3 3 3 3 3

output:

1005594043670359641774

result:

ok single line: '1005594043670359641774'

Test #7:

score: 9.09091
Accepted
time: 130ms
memory: 9772kb

input:

4 4 4 4 4 4 3 3 3 3

output:

666666666666666666666666666665

result:

ok single line: '666666666666666666666666666665'

Test #8:

score: 9.09091
Accepted
time: 126ms
memory: 9784kb

input:

4 5 5 5 5 5 7 8 9 9

output:

100559404367035964177652825361730559404364

result:

ok single line: '100559404367035964177652825361730559404364'

Test #9:

score: 9.09091
Accepted
time: 123ms
memory: 9800kb

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: 124ms
memory: 9664kb

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: 129ms
memory: 9672kb

input:

9 9 9 9 9 9 9 9 9 9

output:

19999199999999919999999991999999999199999999919999999991999999999199999999919999999918

result:

ok single line: '199991999999999199999999919999...1999999999199999999919999999918'