#131951 (C++14) No.441 和か積

• 問題: No.441 和か積
• ユーザー: TautCony
• 提出日時: 2016-11-19 22:59:10
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 5,566 bytes
• コンパイル時間: 839 ms
• コンパイル使用メモリ: 79,068 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-05 10:18:35
• 合計ジャッジ時間: 1,961 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	5 ms; 5,376 KB
testcase_04	AC	5 ms; 5,376 KB
testcase_05	AC	7 ms; 5,376 KB
testcase_06	AC	7 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	WA	-
testcase_10	AC	2 ms; 5,376 KB
testcase_11	WA	-
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	9 ms; 5,376 KB
testcase_21	AC	9 ms; 5,376 KB
testcase_22	AC	9 ms; 5,376 KB
testcase_23	AC	6 ms; 5,376 KB
testcase_24	AC	6 ms; 5,376 KB
testcase_25	AC	6 ms; 5,376 KB
testcase_26	AC	6 ms; 5,376 KB
testcase_27	AC	1 ms; 5,376 KB
testcase_28	AC	4 ms; 5,376 KB
testcase_29	AC	5 ms; 5,376 KB
testcase_30	AC	5 ms; 5,376 KB
testcase_31	AC	3 ms; 5,376 KB
testcase_32	AC	7 ms; 5,376 KB

ソースコード

#include <sstream>
#include <iostream>
#include <vector>

class TNumber
{
public:
    TNumber();
    TNumber(std::string);
    TNumber(unsigned long long);
    ~TNumber();

    TNumber  operator +(const TNumber&);
    TNumber  operator -(const TNumber&);
    TNumber  operator *(const TNumber&);
    TNumber& operator =(const TNumber&);
    TNumber& operator =(const unsigned long long);
    bool operator <(const TNumber&);
    friend std::ostream& operator <<(std::ostream&, const TNumber&);
    friend std::istream& operator >>(std::istream&, TNumber&);
private:
    std::string number;
    size_t _padLeft(std::string &num1, std::string &);
    const std::string _toString(std::vector<char> &);
    const std::string _toString(unsigned long long);
    std::string _removePaddingLeft(std::string);
};

TNumber::TNumber() {}

TNumber::TNumber(std::string s)
{
    s = _removePaddingLeft(s);
    number = s.size() == 0 ? "0" : s;
}

TNumber::TNumber(unsigned long long num)
{
    number = _toString(num);
}

TNumber::~TNumber() {}

std::string TNumber::_removePaddingLeft(std::string input)
{
    size_t i;
    for(i = 0; i < input.size(); ++i)
    {
        if(input[i] > '0' && input[i] <='9') break;//移除左侧的前导零、和非数字字符
    }
    return input.substr(i, input.size() - i);
}

size_t TNumber::_padLeft(std::string & num1, std::string & num2)
{
    //将输入的两数通过前导零使两数位数对齐
    size_t length1 = num1.size();
    size_t length2 = num2.size();
    size_t length = std::max(length1, length2);
    num1 = std::string(length - length1, '0') + num1;
    num2 = std::string(length - length2, '0') + num2;
    return length;
}

const std::string TNumber::_toString(unsigned long long num)
{
    std::stringstream ss;
    ss << num;
    std::string result;
    ss >> result;
    return result;
}

const std::string TNumber::_toString(std::vector<char>& arr)
{
    std::string ans;
    for (std::vector<char>::reverse_iterator iter = arr.rbegin(); iter != arr.rend(); ++iter)
    {
        ans += *iter;
    }
    return ans;
}

TNumber TNumber::operator +(const TNumber &right)
{
    std::string num1 = number;
    std::string num2 = right.number;
    size_t length = _padLeft(num1, num2);
    int carry = 0;
    std::vector<char> result;
    for (int i = static_cast<int>(length) - 1; i >= 0; --i)
    {
        int column = num1[i] - '0' + num2[i] - '0' + carry;
        result.push_back(static_cast<char>(column % 10 + '0'));
        carry = column / 10;
    }
    if (carry != 0)
    {
        result.push_back(static_cast<char>(carry + '0'));
    }
    return TNumber(_toString(result));
}

TNumber TNumber::operator -(const TNumber &right)
{
    std::string num1 = number;
    std::string num2 = right.number;
    size_t length = _padLeft(num1, num2);
    std::vector<char> result;
    for (int i = static_cast<int>(length) - 1; i >= 0; --i)
    {
        int difference = num1[i] - num2[i];
        if (difference >= 0)
        {
            result.push_back(static_cast<char>(difference + '0'));
            continue;
        }
        for (int j = i - 1; j > -1; --j)
        {
            num1[j] = (char) (((num1[j] - '0' + 9) % 10) + '0');
            if (num1[j] - '0' != 9)
            {
                break;
            }
        }
        result.push_back(static_cast<char>(difference + 10 + '0'));
    }
    return TNumber(_toString(result));
}

TNumber TNumber::operator *(const TNumber &right)
{
    std::string num1 = number;
    std::string num2 = right.number;
    size_t length = _padLeft(num1, num2);
    if (length == 1)
    {
        int ans = static_cast<int>(num1[0] - '0')*static_cast<int>(num2[0] - '0');
        if (ans < 10)
        {
            return TNumber(std::string(1, static_cast<char>(ans + '0')));
        }
        else
        {
            std::string temp;
            temp += static_cast<char>(ans / 10 + '0');
            temp += static_cast<char>(ans % 10 + '0');
            return TNumber(temp);
        }
    }
    size_t m0 = (length + 1) / 2;
    size_t m1 = length / 2;

    TNumber num1_l = num1.substr(0, m0);
    TNumber num1_r = num1.substr(m0, length - m0);
    TNumber num2_l = num2.substr(0, m0);
    TNumber num2_r = num2.substr(m0, length - m0);

    TNumber p0 = num1_l * num2_l;
    TNumber p1 = (num1_l + num1_r) * (num2_l + num2_r);
    TNumber p2 = num1_r * num2_r;

    TNumber z1 = p1 - (p0 + p2);

    p0.number += std::string(2 * m1, '0');
    z1.number += std::string(    m1, '0');
    return p0 + z1 + p2;
}

TNumber &TNumber::operator =(const TNumber & right)
{
    if (this == &right) return *this;
    number = right.number;
    return *this;
}
TNumber &TNumber::operator =(const unsigned long long right)
{
    number = _toString(right);
    return *this;
}

bool TNumber::operator<(const TNumber & rhs)
{
    if (this->number.length() == rhs.number.length())
    {
        return this->number < rhs.number;
    }
    return this->number.length() < rhs.number.length();
}

std::ostream &operator <<(std::ostream & os, const TNumber & num)
{
    size_t i;
    for(i = 0; num.number.size(); ++i)
    {
        if(num.number[i] != '0') break;
    }
    os << num.number.substr(i, num.number.size()-i);
    return os;
}

std::istream &operator >>(std::istream &is, TNumber & num)
{
    std::string str;
    is >> str;
    num = TNumber(str);
    return is;
}

using namespace std;

int main() {
    TNumber a, b;
    cin >> a >> b;
    TNumber sum = a + b;
    TNumber mul = a * b;
    cout << (sum<mul?"P":"S") << endl;
    return 0;
}