QOJ.ac
QOJ
QOJ is currently under a maintenance. It might be unavailable in the following a few hours.
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189915 | #1183. Sum of Palindromes | KKT89 | AC ✓ | 63ms | 4848kb | C++17 | 2.6kb | 2023-09-28 01:29:31 | 2023-09-28 01:29:32 |
Judging History
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!