fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #define max_len 1000002
  5. using namespace std;
  6.  
  7. char *str = new char[max_len];
  8. char *rev_str = new char[max_len];
  9. char *residue = new char[max_len];
  10. char *xrev = new char[max_len];
  11. char *a = new char[3];
  12.  
  13. char* str_rev(char *s) {
  14. 	int len=strlen(s);
  15. 	for(int i=0; i<len/2; i++)
  16. 		swap(s[i], s[len-i-1]);
  17. 	return s;
  18. }
  19.  
  20. char* trim(char *s) {
  21. 	int i;
  22. 	for(i=0; s[i] && s[i]=='0'; i++);
  23. 	if(s[i]) strcpy(s, s+i);
  24. 	else strcpy(s, "0");
  25. 	return s;
  26. }
  27.  
  28. int compare(char *a, char *b) {
  29. 	trim(a); trim(b);
  30. 	int alen=strlen(a), blen=strlen(b);
  31. 	if(alen>blen) return 1;
  32. 	if(alen<blen) return -1;
  33. 	for(int i=0; i<alen; i++) {
  34. 		if(a[i]>b[i]) return 1;
  35. 		if(a[i]<b[i]) return -1;
  36. 	}
  37. 	return 0;
  38. }
  39.  
  40. char* add_by_1(char *n) {
  41. 	int len = strlen(n);
  42. 	if(n[len-1] < '9') {
  43. 		n[len-1]++;
  44. 		return n;
  45. 	}
  46. 	int carry=0, p, q=1, sum;
  47. 	for(int i=len-1; i>=0; i--) {
  48. 		p = n[i]-'0';
  49. 		sum = p+q+carry;
  50. 		carry = sum/10;
  51. 		sum %= 10;
  52. 		n[i] = sum+'0';
  53. 		if(i==len-1) q=0;
  54. 	}
  55. 	if(carry) {
  56. 		for(int i=len-1; i>=0; i--)
  57. 			n[i+1] = n[i];
  58. 		n[0] = carry+'0';
  59. 		n[len+1] = 0;
  60. 	}
  61. 	return n;
  62. }
  63.  
  64.  
  65. char* get_palin(char *n) {
  66. 	int len=strlen(n);
  67. 	if(len==1 && n[0]!='9') {
  68. 		n[0]++;
  69. 		return n;
  70. 	}
  71. 	if(len==1 && n[0]=='9') {
  72. 		strcpy(a, "11");
  73. 		return a;
  74. 	}
  75. 	strncpy(rev_str, n, len/2);
  76. 	rev_str[len/2] = 0;
  77. 	if(!(len%2)) strncpy(residue, n+len/2, len/2);
  78. 	else strcpy(residue, n+len/2+1);
  79. 	residue[len/2] = 0;
  80. 	strcpy(xrev, rev_str);
  81. 	if(compare(residue,str_rev(xrev))<0) {
  82.         strcpy(str, rev_str);
  83.         if(len%2) {
  84. 			str[len/2] = n[len/2];
  85. 			str[len/2+1] = 0;
  86.         }
  87.         strcat(str, xrev);
  88. 	}
  89. 	else {
  90. 		if(!(len%2)) {
  91. 			add_by_1(rev_str);
  92. 			strcpy(str, rev_str);
  93. 			if(rev_str[len/2]) {
  94. 				strncpy(xrev, rev_str, len/2);
  95. 				xrev[len/2] = 0;
  96. 				strcat(str, str_rev(xrev));
  97. 			}
  98. 			else strcat(str, str_rev(rev_str));
  99. 		}
  100. 		else {
  101. 			rev_str[len/2] = n[len/2];
  102. 			rev_str[len/2+1] = 0;
  103. 			add_by_1(rev_str);
  104. 			strcpy(str, rev_str);
  105. 				strncpy(xrev, rev_str, len/2);
  106. 				xrev[len/2] = 0;
  107. 				strcat(str, str_rev(xrev));
  108. 		}
  109. 	}
  110. 	return str;
  111. }
  112.  
  113. char input[max_len];
  114. int main() {
  115. 	long long int t;
  116. 	cin>>t;
  117. 	while(t--) {
  118. 		cin>>input;
  119. 		cout<<get_palin(input)<<endl;
  120. 	}
  121. 	return 0;
  122. }
Success #stdin #stdout 0s 8336KB
comments (?)
stdin
copy 
1
100000000000000
stdout
copy 
100000001
https://ideone.com/Wq7YeU
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!