結果

問題 No.441 和か積
コンテスト
ユーザー TautCony
提出日時 2016-11-19 22:59:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,566 bytes
コンパイル時間 842 ms
コンパイル使用メモリ 79,288 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 06:22:45
合計ジャッジ時間 1,995 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 29 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0