I made a biginteger library and I submitted this problem, and it is "wrong answer".
This is my BigInteger Library:
// +----------------------------------
// | BigInteger Library Version 1.1
// | Author: square1001, E869120
// | Date: July 12th, 2016
// | Language: C++11 / C++14
// +---------------------------------
#ifndef ___Class_BasicInteger
#define ___Class_BasicInteger
// ------ Includes ------ //
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
// ------ BasicInteger Algorithms ------ //
std::vector<int> NormalMul(const std::vector<int>&, const std::vector<int>&);
std::vector<int> Karatsuba(const std::vector<int>&, const std::vector<int>&);
// ------ BasicInteger ------ //
class BasicInteger {
private:
// ------ Variable ------ //
int size_;
std::vector<int> v;
// ------ Private Function ------ //
void resize(int size__) {
size_ = size__;
v.resize(size_, 0);
}
int digit() {
int digit = 1;
for (int i = size_ - 1; i >= 1; i--) {
if (v[i] != 0) {
digit = i + 1;
break;
}
}
return digit;
}
void revalue() {
int r = digit();
while (size_ >= r * 2) size_ >>= 1;
v.resize(size_);
}
public:
// ------ Constants ------ //
static const int maxdigit = 4; // maxdigit <= 4
static const int maxvalue = 10000; // maxvalue = pow(10, maxdigit)
// ------ Constructor ------ //
BasicInteger() {
size_ = 1;
v.resize(size_, 0);
}
BasicInteger(std::string &s) {
int r = (s.size() + maxdigit - 1) / maxdigit;
size_ = 1;
while (size_ < r) size_ <<= 1;
v.resize(size_);
reverse(s.begin(), s.end());
int val = 0, cnt = 0, t = 0, p = 1;
for(char c: s) {
val += (c - 48) * p; p *= 10;
if (++cnt == maxdigit) {
v[t++] = val;
val = 0, cnt = 0, p = 1;
}
}
if (cnt > 0) {
v[t] = val;
}
}
BasicInteger(long long x) {
long long y = x; int r = 0;
while (y > 0) y /= 10, r++;
if (x == 0) r = 1;
r = (r + maxdigit - 1) / maxdigit;
size_ = 1;
while (size_ < r) size_ <<= 1;
v.resize(size_);
int t = 0;
while (x > 0) {
v[t++] = x % maxvalue;
x /= maxvalue;
}
}
BasicInteger(const BasicInteger& b) {
size_ = b.size_;
v = b.v;
}
// ------ Functions ------ //
int size() const {
return size_;
}
int digit() const {
for (int i = size_ - 1; i >= 1; i--) {
if (v[i] > 0) return i + 1;
}
return 1;
}
std::string to_string() const {
std::string ret = "";
bool flag = false;
for (int i = size_ - 1; i >= 0; i--) {
bool prev = flag;
if (v[i] > 0) flag = true;
if (flag && !prev) {
ret += std::to_string(v[i]);
}
else if (flag) {
int p = maxvalue / 10, q = v[i];
for (int j = maxdigit - 1; j >= 0; j--) {
ret.push_back(q / p + 48);
q %= p;
p /= 10;
}
}
}
if (!flag) ret = "0";
return ret;
}
// ------ Basic Operators ------ //
BasicInteger& operator=(const BasicInteger& b) {
if (&b != this) {
size_ = b.size_;
v = b.v;
}
return (*this);
}
// ------ Comparision Operators ------ //
friend bool operator==(const BasicInteger& b1, const BasicInteger& b2) {
return b1.v == b2.v;
}
friend bool operator!=(const BasicInteger& b1, const BasicInteger& b2) {
return b1.v != b2.v;
}
friend bool operator<(const BasicInteger& b1, const BasicInteger& b2) {
if (b1.size_ != b2.size_) return b1.size_ < b2.size_;
int n = b1.size_;
for (int i = n - 1; i >= 0; i--) {
if (b1.v[i] != b2.v[i]) return b1.v[i] < b2.v[i];
}
return false;
}
friend bool operator>(const BasicInteger& b1, const BasicInteger& b2) {
if (b1.size_ != b2.size_) return b1.size_ > b2.size_;
int n = b1.size_;
for (int i = n - 1; i >= 0; i--) {
if (b1.v[i] != b2.v[i]) return b1.v[i] > b2.v[i];
}
return false;
}
friend bool operator<=(const BasicInteger& b1, const BasicInteger& b2) {
return !(b1 > b2);
}
friend bool operator>=(const BasicInteger& b1, const BasicInteger& b2) {
return !(b1 < b2);
}
// ------ Addition Operator ------ //
friend BasicInteger operator+(const BasicInteger& b1, const BasicInteger& b2) {
BasicInteger ret(b1);
int n = std::max(b1.size_, b2.size_);
ret.resize(n);
for (int i = 0; i < b2.size_; i++) {
ret.v[i] += b2.v[i];
}
for (int i = 0; i < n - 1; i++) {
if (ret.v[i] >= BasicInteger::maxvalue) {
ret.v[i] -= BasicInteger::maxvalue;
ret.v[i + 1]++;
}
}
if (ret.v[n - 1] >= BasicInteger::maxvalue) {
ret.resize(n << 1);
ret.v[n - 1] -= BasicInteger::maxvalue;
ret.v[n] = 1;
}
return ret;
}
// ------ Subtraction ------ //
friend BasicInteger operator-(const BasicInteger& b1, const BasicInteger& b2) {
assert(b1 >= b2);
BasicInteger ret(b1);
for (int i = 0; i < b2.size_; i++) {
ret.v[i] -= b2.v[i];
}
for (int i = 0; i < ret.size_; i++) {
if (ret.v[i] < 0) {
ret.v[i] += BasicInteger::maxvalue;
ret.v[i + 1]--;
}
}
ret.revalue();
return ret;
}
// ------ Multiplication ------ //
friend BasicInteger operator*(const BasicInteger& b1, const BasicInteger& b2) {
BasicInteger ret;
BasicInteger b3(b1 < b2 ? b2 : b1); // large
BasicInteger b4(b1 < b2 ? b1 : b2); // small
int d1 = b3.size_, d2 = b4.size_;
ret.resize(d1 << 1);
for (int i = 0; i < d1; i += d2) {
std::vector<int> sub(b3.v.begin() + i, b3.v.begin() + i + d2);
std::vector<int> res = Karatsuba(sub, b4.v);
for (int j = 0; j < (d2 << 1); j++) {
ret.v[j + i] += res[j];
}
}
ret.revalue();
return ret;
}
// ------ In / Out Operator ------ //
friend std::istream& operator>>(std::istream& is, BasicInteger& b) {
std::string res;
is >> res;
b = BasicInteger(res);
return is;
}
friend std::ostream& operator<<(std::ostream& os, const BasicInteger& b) {
os << b.to_string();
return os;
}
};
// ------ Multiplication Algorithms ------ //
inline std::vector<int> NormalMul(const std::vector<int>& b1, const std::vector<int>& b2) {
int n = b1.size(); // b1 and b2 is the same size!
std::vector<long long> ret(n << 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ret[i + j] += b1[i] * b2[j];
}
}
for (int i = 0; i < (n << 1) - 1; i++) {
ret[i + 1] += ret[i] / BasicInteger::maxvalue;
ret[i] %= BasicInteger::maxvalue;
}
std::vector<int> res(n << 1);
for (int i = 0; i < (n << 1); i++) res[i] = ret[i];
return res;
}
inline std::vector<int> Karatsuba(const std::vector<int>& b1, const std::vector<int>& b2) {
int n = b1.size(); // b1 and b2 is the same size!
if (n <= 128) return NormalMul(b1, b2);
std::vector<int> b3(b1.begin(), b1.begin() + (n >> 1));
std::vector<int> b4(b1.begin() + (n >> 1), b1.end());
std::vector<int> b5(b2.begin(), b2.begin() + (n >> 1));
std::vector<int> b6(b2.begin() + (n >> 1), b2.end());
std::vector<int> z0 = Karatsuba(b3, b5);
std::vector<int> z2 = Karatsuba(b4, b6);
int f1 = 0;
for (int i = (n >> 1) - 1; i >= 0; i--) {
if (b3[i] < b4[i]) f1 = 1;
else if (b3[i] > b4[i]) break;
}
int f2 = 0;
for (int i = (n >> 1) - 1; i >= 0; i--) {
if (b5[i] < b6[i]) f2 = 1;
else if (b5[i] > b6[i]) break;
}
if (f1) std::swap(b3, b4);
if (f2) std::swap(b5, b6);
std::vector<int> r0(b3);
for (int i = 0; i < (n >> 1); i++) {
r0[i] -= b4[i];
if (r0[i] < 0) {
r0[i] += BasicInteger::maxvalue;
r0[i + 1]--;
}
}
std::vector<int> r1(b5);
for (int i = 0; i < (n >> 1); i++) {
r1[i] -= b6[i];
if (r1[i] < 0) {
r1[i] += BasicInteger::maxvalue;
r1[i + 1]--;
}
}
std::vector<int> r2 = Karatsuba(r0, r1);
std::vector<int> z1(z0);
z1.resize(n << 1, 0);
for (int i = 0; i < n; i++) {
z1[i] += z2[i];
if (z1[i] >= BasicInteger::maxvalue) {
z1[i] -= BasicInteger::maxvalue;
z1[i + 1]++;
}
}
for (int i = 0; i < n; i++) {
z1[i] += ((f1 + f2 == 1) ? r2[i] : -r2[i]);
if (z1[i] >= BasicInteger::maxvalue) {
z1[i] -= BasicInteger::maxvalue;
z1[i + 1]++;
}
if (z1[i] < 0) {
z1[i] += BasicInteger::maxvalue;
z1[i + 1]--;
}
}
std::vector<int> ret(z0);
ret.resize(n << 1, 0);
for (int i = 0; i < (n << 1) - (n >> 1); i++) ret[i + (n >> 1)] += z1[i];
for (int i = 0; i < n; i++) ret[i + n] += z2[i];
for (int i = 0; i < (n << 1) - 1; i++) {
int cnt = 0;
while (ret[i] >= BasicInteger::maxvalue) {
ret[i] -= BasicInteger::maxvalue;
cnt++;
}
if (cnt) {
ret[i + 1] += cnt;
}
}
return ret;
}
#endif
If you find any bug, please reply.
Thank you for reading.