QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164936#6407. Classical A+B Problem3360550356TL 967ms8568kbC++141.9kb2023-09-05 14:50:102023-09-05 14:50:11

Judging History

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

  • [2023-09-05 14:50:11]
  • 评测
  • 测评结果:TL
  • 用时:967ms
  • 内存:8568kb
  • [2023-09-05 14:50:10]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N=2e5+10;
const int mod=1e9+7;
const int INF=1e9;

string s; 
int len; 
int a[N],b[N],c[N];
string ansa,ansb; 

bool fun2(string str1,string str2){			//s1-s2

	for(int i=0;i<N;i++)a[i]=b[i]=c[i]=0;
    if (str1<str2&&str1.size() == str2.size()){
        return false;
    }
    for (int i = 0; i < str1.size(); i ++)
        a[str1.size()-1-i] = str1[i] - '0';
    for (int i = 0; i < str2.size(); i ++)
        b[str2.size()-i-1] = str2[i] - '0';
        
    int ans = max(str1.size(), str2.size());
    for (int i = 0; i < ans; i ++){
        if (a[i] < b[i]){
            a[i+1] -= 1; // 向前位借一位
            a[i] += 10;  // 后一位就得加10
        }
		c[i] = a[i] - b[i];  // 之后就是正常减法了
//		cout<<i<<" "<<a[i]<<" "<<b[i]<<" "<<c[i]<<endl;
		if(i&&c[i]!=c[i-1]&&c[i]){
			return false;			//提前中断,前导0不能作为判断条件 
		}
    }
    while (c[ans-1] == 0 && ans > 1)ans -= 1; 
    
    if(ans==1&&!c[0])return false;
    
    for (int i = 1; i < ans; i ++){
    		if(c[i]!=c[i-1]){
    			return false;
		} 
	}
	
    for (int i = 0; i < ans; i ++){
    	ansb+=('0'+c[ans-1-i]);
	}    
	return true;
} 

bool fun1(int l,int x){		//预处理 
	ansa="";
	ansb="";
	string t;
	char c='0'+x; 
	for(int i=0;i<l;i++){
		t+=c;
	}
	
	ansa=t;
	//做一下高精度减法,s-t 
	int flag=fun2(s,t);
	if(!flag)return false;
	else {
		return true;
	}
}



void solve(){
	cin>>s;
	len=s.length();
	

	//1.枚举a的长度要么一样,要么小1,2.枚举数字1--9
	for(int i=len;i>=len-1;i--){
		for(int j=9;j>=1;j--){
			if(fun1(i,j)){
				cout<<ansa<<" "<<ansb<<endl;
				return;
			}
		}	
	} 
	
	
}




signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) {
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 8568kb

input:

6
2
786
1332
89110
2333333
10000000000000000000000000001

output:

1 1
777 9
999 333
88888 222
2222222 111111
9999999999999999999999999999 2

result:

ok ok (6 test cases)

Test #2:

score: 0
Accepted
time: 102ms
memory: 8332kb

input:

100
854
77777777781111111111111111110
44444450
11111111111111333
2310
5
333333333333333333333343332
888999
10
11113333
335
77779
88888888888888888888889111111111111111111110
55555555555555777777
72222222222222222222221
666
5777
1111555555
444444444544444444443
88888888888891111111111110
673332
97
77...

output:

777 77
77777777777777777777777777777 3333333333333333333
44444444 6
11111111111111111 222
2222 88
4 1
333333333333333333333333333 9999
888888 111
9 1
11111111 2222
333 2
77777 2
88888888888888888888888888888888888888888888 222222222222222222222
55555555555555555555 222222
66666666666666666666666 555...

result:

ok ok (100 test cases)

Test #3:

score: 0
Accepted
time: 967ms
memory: 8372kb

input:

1000
999999
1199
888891
33333333344
6
55555633333333333333333333333333332
444999
333333333333333343333332
10000000055554
76666666666666666666666665
2310
55555633332
166666666666666
111111111111111888888888888888888
891
8888889333333333332
7
555555556666666666
22266666666666
7778554
667
5555555556222...

output:

888888 111111
1111 88
888888 3
33333333333 11
5 1
55555555555555555555555555555555555 77777777777777777777777777777
444444 555
333333333333333333333333 9999999
9999999999999 55555
66666666666666666666666666 9999999999999999999999999
2222 88
55555555555 77777
111111111111111 55555555555555
1111111111...

result:

ok ok (1000 test cases)

Test #4:

score: -100
Time Limit Exceeded

input:

10000
321
7777777854
2
3666
55566666666
6666666699
49
2888888
10000888888888888888887
5654
99
6555554
10
5
222222255555
2777
8
777779
3333333333377777777
77
667666665
110
9
7777777777777777788888888888
8
6
444444532
555556555555555555554
10000099998
610
1000000000000000055554
34444
5555666666
188888...

output:

222 99
7777777777 77
1 1
3333 333
55555555555 11111111
6666666666 33
44 5
2222222 666666
9999999999999999999999 888888888888888888
5555 99
88 11
5555555 999999
9 1
4 1
222222222222 33333
2222 555
7 1
777777 2
3333333333333333333 44444444
66 11
666666666 999999
99 11
8 1
7777777777777777777777777777 ...

result: