QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189915#1183. Sum of PalindromesKKT89AC ✓63ms4848kbC++172.6kb2023-09-28 01:29:312023-09-28 01:29:32

Judging History

This is the latest submission verdict.

  • [2023-09-28 01:29:32]
  • Judged
  • Verdict: AC
  • Time: 63ms
  • Memory: 4848kb
  • [2023-09-28 01:29:31]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

bool comp(string a,string b){
	if(a==b)return true;
	if(a.size()>b.size())return true;
	else if(b.size()>a.size())return false;
	else return a>b;
}

string add(string a,string b){
	int maxlen=max(a.size(),b.size())+1;
	vector<int> ret(maxlen,0);
	string ans="";
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for(int i=0;i<a.size();i++){
		ret[i]+=(a[i]-'0');
	}
	for(int i=0;i<b.size();i++){
		ret[i]+=(b[i]-'0');
	}
	for(int i=0;i<maxlen-1;i++){
		ans+=(ret[i]%10)+'0';
		ret[i+1]+=ret[i]/10;
	}
	if(ret[maxlen-1]){
		ans+=ret[maxlen-1]+'0';
	}
	reverse(ans.begin(),ans.end());
	return ans;
}

string sub(string a,string b){
	bool minus=0;
	if(!comp(a,b)){
		swap(a,b);
		minus=1;
	}
	int maxlen=max(a.size(),b.size());
	vector<int> ret(maxlen,0);
	string ans="";
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for(int i=0;i<a.size();i++){
		ret[i]=a[i]-'0';
	}
	for(int i=0;i<b.size();i++){
		ret[i]-=b[i]-'0';
	}
	for(int i=0;i<maxlen;i++){
		while(ret[i]<0){
			ret[i]+=10;
			ret[i+1]--;
		}
		ans+=(ret[i]+'0');
	}
	reverse(ans.begin(),ans.end());
	int cnt=0;
	while(ans[cnt]=='0'&&cnt!=ans.size()-1)cnt++;
	return (minus?"-":"")+ans.substr(cnt);
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int q; cin >> q;
	vector<string> res;
	string s,t,r,rr;
	while(q--){
		cin >> s;
		res.clear();
		while(s!="0"){
			if(s.size()==1){
				res.push_back(s); break;
			}
			int sz=s.size();
			if(sz%2==1){
				r=s.substr(0,sz/2);
				rr=r; reverse(rr.begin(), rr.end());
				t=r; t+=s[sz/2]; t+=rr;
				if(sub(s,t)[0]!='-'){
					s=sub(s,t);
					res.push_back(t);
				}
				else{
					r=sub(r,"1");
					if(r.size()<sz/2 or r=="0"){
						t=string(sz-1,'9');
					}
					else{
						rr=r;
						reverse(rr.begin(), rr.end());
						t=r; t+=s[sz/2]; t+=rr;
					}
					s=sub(s,t);
					res.push_back(t);
				}
			}
			else{
				r=s.substr(0,sz/2);
				rr=r; reverse(rr.begin(), rr.end());
				t=r+rr;
				if(sub(s,t)[0]!='-'){
					s=sub(s,t);
					res.push_back(t);
				}
				else{
					r=sub(r,"1");
					if(r.size()<sz/2 or r=="0"){
						t=string(sz-1,'9');
					}
					else{
						rr=r;
						reverse(rr.begin(), rr.end());
						t=r+rr;
					}
					s=sub(s,t);
					res.push_back(t);
				}
			}
		}
		cout << res.size() << "\n";
		for(string r:res){
			cout << r << "\n";
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3588kb

input:

2
378
2020

output:

2
373
5
3
2002
11
7

result:

ok OK!

Test #2:

score: 0
Accepted
time: 63ms
memory: 4848kb

input:

10128
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
10...

output:

1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
9
1
1
11
2
11
1
2
11
2
2
11
3
2
11
4
2
11
5
2
11
6
2
11
7
2
11
8
2
11
9
3
11
9
1
1
22
2
22
1
2
22
2
2
22
3
2
22
4
2
22
5
2
22
6
2
22
7
2
22
8
2
22
9
3
22
9
1
1
33
2
33
1
2
33
2
2
33
3
2
33
4
2
33
5
2
33
6
2
33
7
2
33
8
2
33
9
3
33
9
1
1
44
2
44
1
2
44
2
2
44
3
2...

result:

ok OK!