oj.uz

Submission #490945

# Submission time Handle Problem Language Result Execution time Memory
490945 2021-11-30T00:56:13 Z TranGiaHuy1508 Multiply (CEOI17_mul) C++17
40 / 100
 2000 ms 556 KB 
// C++ Template

#include "bits/stdc++.h"
using namespace std;

// Type
typedef long long ll;
typedef long double ld;

// Pair/Vector
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

// Priority Queue
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

// Macro
#define stat(x) (x) && cout << "YES\n" || cout << "NO\n";
#ifdef LOCAL
    #define debug(x) cout << #x << " = " << x << "\n";
#else
    #define debug(x) ;
#endif

// Custom output
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){
    out << "(" << x.first << ", " << x.second << ")";
    return out;
}

template <class T>
ostream& operator << (ostream& out, vector<T> x){
    out << "[";
    for (int i=0; i<x.size(); i++){
        if (i) out << ", ";
        out << x[i];
    }
    out << "]";
    return out;
}

void fastio(string finp = "", string fout = ""){
    if (fopen(finp.c_str(), "r")){
        freopen(finp.c_str(), "r", stdin);
        freopen(fout.c_str(), "w", stdout);
    }
}

// Const
const int interactive = 0;
const ld PI = acos(-1.0);
const ll allmod[2] = {int(1e9)+7, 998244353};
const ll mod = allmod[0];
const ll maxn = 2e5;
const ll inf = 1e18;
const int multitest = 0;

#define int long long

struct BigNum{
	string value;
	int sign;

	// Assignment
	BigNum(string x){
		if (x[0] == '-'){
			this->sign = -1;
			this->value = x.substr(1, x.length() - 1);
		}
		else{
			this->sign = 1;
			this->value = x;
		}
		ref(*this);
	}

	BigNum(int x){
		if (x < 0){
			this->sign = -1;
			this->value = "";
			int tmp = abs(x);
			while (tmp > 0){
				this->value += char(tmp%10 + 48);
				tmp /= 10;
			}
			reverse(this->value.begin(), this->value.end());
		}
		else{
			this->sign = 1;
			this->value = "";
			int tmp = abs(x);
			while (tmp > 0){
				this->value += char(tmp%10 + 48);
				tmp /= 10;
			}
			reverse(this->value.begin(), this->value.end());
		}
		ref(*this);
	}

	BigNum(){
		this->sign = 1;
		this->value = "0";
	}

	// I/O

	friend ostream& operator << (ostream& out, const BigNum &x){
		if (x.sign == -1){
			out << "-" << x.value;
		}
		else{
			out << x.value;
		}
		return out;
	}
	
	friend istream& operator >> (istream& in, BigNum &x){
		string tmp; cin >> tmp;
		x = BigNum(tmp);

		return in;
	}

	// Strip leading 0s

	void ref(BigNum &x){
		string tmp = x.value;
		int i=0;
		while (i < (ll)tmp.length() && tmp[i] == '0') i++;

		if (i >= (ll)tmp.length()){
			tmp = "";
		}
		else{
			tmp = tmp.substr(i, tmp.length() - i);
		}

		if (!tmp.length()) tmp = "0";

		x.value = tmp;
	}

	void ref(string &x){
		string tmp = x;
		int i=0;
		while (i < (ll)tmp.length() && tmp[i] == '0') i++;

		if (i >= (ll)tmp.length()){
			tmp = "";
		}
		else{
			tmp = tmp.substr(i, tmp.length() - i);
		}

		if (!tmp.length()) tmp = "0";

		x = tmp;
	}

	// Reverse sign

	BigNum rev(BigNum x){
		x.sign = (x.sign) * (-1);
		return x;
	}

	// Operator overload

	BigNum operator + (BigNum y){
		BigNum x = *this;
		BigNum res;

		if (x.sign == y.sign){
			res.sign = x.sign;
			res.value = add(x.value, y.value);
		}
		else{
			if (x.sign == 1){
				// return x - abs(y)
				y.sign = 1;
				return x - y;
			}
			else{
				// return y - abs(x)
				x.sign = 1;
				return y - x;
			}
		}
		return res;
	}

	BigNum operator - (BigNum y){
		BigNum x = *this;
		BigNum res;

		if (x.sign == y.sign){
			res.value = sub(x.value, y.value);

			if (res.value[0] == '-'){
				res.sign = -1;
				res.value = res.value.substr(1, res.value.length()-1);
			}
			else{
				res.sign = 1;
			}

			res.sign *= x.sign;

			return res;
		}
		else{
			if (x.sign == 1){
				y.sign = 1;
				return x + y;
			}
			else{
				x.sign = 1;
				return rev(x + y);
			}
		}
	}

	BigNum operator * (BigNum y){
		BigNum x = *this;
		BigNum res;

		res.value = mult(x.value, y.value);
		if (x.sign != y.sign) res.sign = -1;
		else res.sign = 1;

		return res;
	}

	BigNum operator / (BigNum y){
		BigNum x = *this;
		BigNum res;
		res.sign = x.sign * y.sign;

		if (y.value == "" || y.value == "0"){
			throw "Divided by zero";
		}

		res.value = div(x.value, y.value).first;
		return res;
	}

	BigNum operator % (BigNum y){
		BigNum x = *this;
		BigNum res;
		res.sign = x.sign;

		if (y.value == "" || y.value == "0"){
			throw "Divided by zero";
		}

		res.value = div(x.value, y.value).second;
		return res;
	}

	// String operator

	string add(string x, string y){ // Add 2 string which represent 2 non-negative numbers
		string res = "";

		reverse(x.begin(), x.end());
		reverse(y.begin(), y.end());

		int carry = 0;
		for (int i=0; i <= (ll)max(x.length(), y.length()); i++){
			int t1, t2;
			if (i >= (ll)x.length()){
				t1 = 0;
			}
			else{
				t1 = ll(x[i]) - 48;
			}
			if (i >= (ll)y.length()){
				t2 = 0;
			}
			else{
				t2 = ll(y[i]) - 48;
			}

			int val = t1 + t2 + carry;

			res += char(val%10 + 48);

			carry = val/10;
		}

		reverse(res.begin(), res.end());
		ref(res);

		return res;
	}

	string sub(string x, string y){ // Subtract 2 string which represent 2 non-negative numbers
		string res = "";

		reverse(x.begin(), x.end());
		reverse(y.begin(), y.end());

		int carry = 0;
		for (int i=0; i <= (ll)max(x.length(), y.length()); i++){
			int t1, t2;
			if (i >= (ll)x.length()){
				t1 = 0;
			}
			else{
				t1 = ll(x[i]) - 48;
			}
			if (i >= (ll)y.length()){
				t2 = 0;
			}
			else{
				t2 = ll(y[i]) - 48;
			}

			int val = t1 - t2 - carry;

			if (val < 0){
				val += 10;
				carry = 1;
			}
			else carry = 0;

			res += char(val + 48);
		}

		reverse(res.begin(), res.end());
		ref(res);

		if (carry == 1){
			reverse(x.begin(), x.end());
			reverse(y.begin(), y.end());
			return "-" + sub(y, x);
		}

		return res;
	}

	string mult(string x, string y){ // Multiply 2 string which represent 2 non-negative numbers
		string res = "0";
		for (int i=y.length()-1; i>=0; i--){
			string tmp = "0";
			for (int j = ll(y[i])-48; j > 0; j--){
				tmp = add(tmp, x);
			}
			for (int j=0; j<y.length() - 1 - i; j++) tmp = tmp + "0";
			res = add(res, tmp);
		}
		ref(res);
		return res;
	}

	pair<string, string> div(string x, string y){ // Divide 2 string which represent 2 postive numbers, return {quotient, remainder}
		string crr = "";
		string res = "";
		string prev;

		if (y == "" || y == "0"){
			throw "Divided by zero";
		}

		for (int i=0; i<x.length(); i++){
			crr += x[i];
			int cnt = -1;
			while (crr[0] != '-'){
				prev = crr;
				crr = sub(crr, y);
				cnt++;
			}
			crr = prev;
			res += char(cnt + 48);
		}

		ref(res);
		ref(crr);
		return {res, crr};
	}
};

void main_program(){
    int n, m; cin >> n >> m;
    BigNum a, b; cin >> a >> b;
    cout << a*b;
}

void pre_main(){
    
}

signed main(){

    #ifdef LOCAL
        auto start_time = chrono::high_resolution_clock::now();
    #endif

    if (!interactive) {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
    #ifndef ONLINE_JUDGE
        fastio(".inp", ".out");
    #endif

    int t = 1;
    if (multitest) cin >> t;
    pre_main();
    while (t--) main_program();

    #ifdef LOCAL
        auto end_time = chrono::high_resolution_clock::now();
        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
        cout << "\n[" << duration << "ms]\n";
    #endif
}

Compilation message

mul.cpp: In member function 'std::string BigNum::mult(std::string, std::string)':
mul.cpp:354:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  354 |    for (int j=0; j<y.length() - 1 - i; j++) tmp = tmp + "0";
      |                  ~^~~~~~~~~~~~~~~~~~~
mul.cpp: In member function 'std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > BigNum::div(std::string, std::string)':
mul.cpp:370:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  370 |   for (int i=0; i<x.length(); i++){
      |                 ~^~~~~~~~~~~
mul.cpp: In function 'void fastio(std::string, std::string)':
mul.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(finp.c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mul.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(fout.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Execution timed out 2089 ms 556 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Execution timed out 2089 ms 556 KB Time limit exceeded
12 Halted 0 ms 0 KB -