Submission #1325107

#TimeUsernameProblemLanguageResultExecution timeMemory
1325107Jawad_Akbar_JJ홀-짝 수열 (IZhO11_oddeven)C++20
100 / 100
3 ms332 KiB
#include <iostream>
#include <vector>

using namespace std;
const int M = 10, len = 1;

struct BigInt{
	vector<int> a;

	
	void operator = (int k){
		a.clear();
		do{
			a.push_back(k % M), k /= M;
		}
		while (k);
	}

	void operator += (BigInt X){
		BigInt res;

		for (int i=0, c = 0;i<max(a.size(), X.a.size()) or c > 0;i++){
			if (i < a.size())
				c += a[i];
			if (i < X.a.size())
				c += X.a[i];
			res.a.push_back(c % M), c /= M;
		}
		swap(a, res.a);
	}

	void operator -= (BigInt X){
		BigInt res;

		for (int i=0, fl = 0;i<a.size();i++){
			int c = 0;
			if (i < X.a.size())
				c += X.a[i];

			a[i] -= fl, fl = 0;
			a[i] -= c;
			if (a[i] < 0)
				a[i] += M, fl = 1;				
		}
	}

	void operator *= (BigInt X){
		BigInt res;
		while (res.a.size() < a.size() + X.a.size())
			res.a.push_back(0);
		
		for (int i=0;i<a.size();i++){
			for (int j=0;j<X.a.size();j++)
				res.a[i+j] += a[i] * X.a[j] % M, res.a[i+j+1] += (a[i] * X.a[j]) / M;
		}
		for (int i=0;i+1<res.a.size();i++)
			res.a[i+1] += res.a[i] / M, res.a[i] %= M;
		while (res.a.size() > 1 and res.a.back() == 0)
			res.a.pop_back();
		swap(a, res.a);
	}

	void operator /= (int two){
		BigInt res;

		for (int i=a.size() - 1, cr = 0;i + 1; i--){
			cr = cr * M + a[i];
			if (cr / 2 != 0 or res.a.size() > 0)
				res.a.insert(res.a.begin(), cr / 2), cr %= 2;
		}
		if (res.a.size() == 0)
			res.a.push_back(0);
		swap(a, res.a);
	}

	bool operator < (BigInt X){
		if (a.size() != X.a.size())
			return a.size() < X.a.size();
		for (int i=a.size()-1;i>=0;i--)
			if (a[i] != X.a[i])
				return a[i] < X.a[i];
		return 0;
	}
	
};

void print(BigInt X){
	for (int i=X.a.size();i;i--){
		string s = to_string(X.a[i-1]);
		while (s.size() < len)
			s = '0' + s;
		cout<<s;
	}
	cout<<'\n';
}

int main(){
	BigInt N, one, two, ten, d, l, r, mid, A;
	one = 1, two = 2, ten = 10, N = 0;
	
	string s;
	cin>>s;

	for (auto i : s)
		d = i - '0', N *= ten, N += d;

	l = 0, r = N, N *= two;
	
	while (1){
		mid = l, mid += r, mid /= 2;
		if (l.a == mid.a)
			break;
		A = mid,  A += one, A *= mid;

		if (A < N)
			l = mid;
		else
			r = mid;
	}
	N -= r;
	print(N);

}
#Verdict Execution timeMemoryGrader output
Fetching results...