QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#164936 | #6407. Classical A+B Problem | 3360550356 | TL | 967ms | 8568kb | C++14 | 1.9kb | 2023-09-05 14:50:10 | 2023-09-05 14:50:11 |
Judging History
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 ...