oj.uz

Submission #548267

# Submission time Handle Problem Language Result Execution time Memory
548267 2022-04-12T20:36:36 Z racsosabe Odd-even (IZhO11_oddeven) C++14
100 / 100
 3 ms 468 KB 
#include<bits/stdc++.h>
using namespace::std;

struct BigInteger{
	vector<int> v;

	BigInteger(){
		v.emplace_back(0);
	}
	BigInteger(int x){
		if(x == 0){
			v.emplace_back(0);
			return;
		}
		while(x){
			v.emplace_back(x % 10);
			x /= 10;
		}
	}

	BigInteger(vector<int> &v){
		this -> v = v;
	}

	BigInteger(string s){
		for(int i = s.size() - 1; i >= 0; i--){
			v.emplace_back(s[i] - '0');
		}
	}

	BigInteger operator + (const BigInteger b){
		vector<int> res(max(v.size(), b.v.size()));
		for(int i = 0; i < res.size(); i++){
			if(i < v.size()) res[i] += v[i];
			if(i < b.v.size()) res[i] += b.v[i];
		}
		for(int i = 0; i < res.size(); i++){
			if(res[i] >= 10){
				if(i + 1 < res.size()) res[i + 1] += res[i] / 10;
				else res.emplace_back(res[i] / 10);
				res[i] %= 10;
			}
		}
		return BigInteger(res);
	}

	BigInteger operator * (const BigInteger b){
		vector<int> res(v.size() + b.v.size());
		for(int i = 0; i < v.size(); i++){
			for(int j = 0; j < b.v.size(); j++){
				res[i + j] += v[i] * b.v[j];
			}
		}
		for(int i = 0; i < res.size(); i++){
			if(res[i] >= 10){
				if(i + 1 < res.size()) res[i + 1] += res[i] / 10;
				else res.emplace_back(res[i] / 10);
				res[i] %= 10;
			}
		}
		while(res.size() > 1 and res.back() == 0) res.pop_back();
		return BigInteger(res);
	}

	BigInteger operator - (const BigInteger b){
		vector<int> res(max(v.size(), b.v.size()));
		for(int i = 0; i < res.size(); i++){
			if(i < v.size()) res[i] += v[i];
			if(i < b.v.size()) res[i] -= b.v[i];
		}
		for(int i = 0; i < res.size(); i++){
			if(res[i] < 0){
				res[i] += 10;
				res[i + 1] -= 1;
			}
		}
		while(res.size() > 1 and res.back() == 0) res.pop_back();
		return BigInteger(res);
	}

	bool operator < (const BigInteger b){
		if(v.size() == b.v.size()){
			for(int i = v.size() - 1; i >= 0; i--){
				if(v[i] != b.v[i]) return v[i] < b.v[i];
			}
			return false;
		}
		return v.size() < b.v.size();
	}

	bool operator <= (const BigInteger b){
		if(v.size() == b.v.size()){
			for(int i = v.size() - 1; i >= 0; i--){
				if(v[i] != b.v[i]) return v[i] < b.v[i];
			}
			return true;
		}
		return v.size() < b.v.size();
	}

	void half(){
		for(int i = v.size() - 1; i >= 0; i--){
			if(v[i] & 1) v[i - 1] += 10;
			v[i] /= 2;
		}
		while(v.size() > 1 and v.back() == 0) v.pop_back();
	}

	void print(){
		for(int i = v.size() - 1; i >= 0; i--) cout << char('0' + v[i]);
		cout << endl;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	BigInteger rt;
	BigInteger n(s);
	vector<BigInteger> pot;
	pot.emplace_back(BigInteger("1"));
	while(pot.back() <= n){
		pot.emplace_back(pot.back() + pot.back());
	}
	for(int i = pot.size() - 1; i >= 0; i--){
		BigInteger new_value = (rt + pot[i]) * (rt + pot[i] + pot[0]);
		new_value.half();
		if(new_value < n){
			rt = rt + pot[i];
		}
	}
	BigInteger at = pot[1] * n - rt - pot[0];
	at.print();
	return 0;
}

Compilation message

oddeven.cpp: In member function 'BigInteger BigInteger::operator+(BigInteger)':
oddeven.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int i = 0; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~
oddeven.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    if(i < v.size()) res[i] += v[i];
      |       ~~^~~~~~~~~~
oddeven.cpp:35:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    if(i < b.v.size()) res[i] += b.v[i];
      |       ~~^~~~~~~~~~~~
oddeven.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int i = 0; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~
oddeven.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(i + 1 < res.size()) res[i + 1] += res[i] / 10;
      |        ~~~~~~^~~~~~~~~~~~
oddeven.cpp: In member function 'BigInteger BigInteger::operator*(BigInteger)':
oddeven.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
oddeven.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int j = 0; j < b.v.size(); j++){
      |                   ~~^~~~~~~~~~~~
oddeven.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i = 0; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~
oddeven.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if(i + 1 < res.size()) res[i + 1] += res[i] / 10;
      |        ~~~~~~^~~~~~~~~~~~
oddeven.cpp: In member function 'BigInteger BigInteger::operator-(BigInteger)':
oddeven.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int i = 0; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~
oddeven.cpp:68:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    if(i < v.size()) res[i] += v[i];
      |       ~~^~~~~~~~~~
oddeven.cpp:69:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    if(i < b.v.size()) res[i] -= b.v[i];
      |       ~~^~~~~~~~~~~~
oddeven.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i = 0; i < res.size(); i++){
      |                  ~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 320 KB Output is correct
19 Correct 3 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 468 KB Output is correct