답안 #93796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93796 2019-01-11T12:22:28 Z Noam527 홀-짝 수열 (IZhO11_oddeven) C++17
100 / 100
3 ms 504 KB
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

struct bigint {
	const int lim = 10000, g = 4;
	vector<int> a;
	bigint() {
		a.clear();
	}
	bigint(string s) {
		a.clear();
		reverse(s.begin(), s.end());
		for (int i = 0; i < s.size(); i += g) {
			a.push_back(0);
			for (int j = min((int)s.size() - 1, i + g - 1); j >= i; j--) {
				a.back() = 10 * a.back() + (s[j] - '0');
			}
		}
	}
	bigint(int val) {
		a.clear();
		while (val) {
			a.push_back(val % lim);
			val /= lim;
		}
	}
	bigint(vector<int> &b) {
		a = b;
	}
	bigint(vector<ll> &b) {
		a.clear();
		a.resize(b.size());
		for (int i = 0; i < b.size(); i++) a[i] = b[i];
	}
	void clear(vector<ll> &b) const  {
		ll rem = 0;
		for (auto &i : b) {
			i += rem;
			rem = i / lim;
			i %= lim;
		}
		while (rem) {
			b.push_back(rem % lim);
			rem /= lim;
		}
	}
	void clear(vector<int> &b) const  {
		int rem = 0;
		for (auto &i : b) {
			i += rem;
			rem = i / lim;
			i %= lim;
		}
		while (rem) {
			b.push_back(rem % lim);
			rem /= lim;
		}
	}
	void clear() {
		clear(this->a);
	}
	bigint operator + (const bigint &x) const {
		vector<int> b;
		for (int i = 0; i < x.a.size() || i < a.size(); i++) {
			b.push_back(0);
			if (i < x.a.size()) b[i] += x.a[i];
			if (i < a.size()) b[i] += a[i];
		}
		clear(b);
		return bigint(b);
	}
	bigint operator + (int val) const {
		bigint b(val);
		return *this + b;
	}
	bigint operator - (const bigint &x) const {
		bigint b = *this;
		int sub = 0;
		for (int i = 0; i < b.a.size(); i++) {
			b.a[i] -= sub; sub = 0;
			if (i < x.a.size()) b.a[i] -= x.a[i];
			if (b.a[i] < 0) {
				b.a[i] += lim;
				sub = 1;
			}
		}
		while (b.a.size() && b.a.back() == 0) b.a.pop_back();
		return b;
	}
	bigint operator - (int val) const {
		bigint b(val);
		return *this - b;
	}
	bigint operator * (const bigint &x) const {
		vector<ll> b((int)this->a.size() + (int)x.a.size() - 1);
		for (int i = 0; i < a.size(); i++) for (int j = 0; j < x.a.size(); j++)
			b[i + j] += a[i] * x.a[j];
		clear(b);
		return bigint(b);
	}
	bigint operator * (int val) const {
		bigint b(val);
		return *this * b;
	}
	bigint operator / (int val) const {
		bigint b = *this;
		ll add = 0;
		for (int i = (int)b.a.size() - 1; i >= 0; i--) {
			b.a[i] += add * lim;
			add = b.a[i] % val;
			b.a[i] /= val;
		}
		while (b.a.size() && b.a.back() == 0) b.a.pop_back();
		clear(b.a);
		return b;
	}
	void operator = (bigint x) {
		a = x.a;
	}
	bool operator < (const bigint &x) const {
		if (a.size() != x.a.size()) return a.size() < x.a.size();
		for (int i = (int)a.size() - 1; i >= 0; i--) {
			if (a[i] != x.a[i]) return a[i] < x.a[i];
		}
		return false;
	}
	void print() {
		if (a.size() == 0) return;
		cout << a.back();
		int tmp;
		for (int i = (int)a.size() - 2; i >= 0; i--) {
			tmp = lim / 10;
			while (tmp) {
				cout << (a[i] / tmp) % 10;
				tmp /= 10;
			}
		}
	}
};

string s;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s;
	bigint n(s);
	n = n * 2;
	bigint lo("0"), hi = n, mid, tmp;
	while (lo < hi) {
		mid = (lo + hi + 1) / 2;
		tmp = mid + 1;
		if (mid * tmp < n) lo = mid;
		else hi = mid - 1;
	}
	bigint ans = n - lo - 1;
	ans.print();
}

Compilation message

oddeven.cpp: In constructor 'bigint::bigint(std::__cxx11::string)':
oddeven.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i += g) {
                   ~~^~~~~~~~~~
oddeven.cpp: In constructor 'bigint::bigint(std::vector<long long int>&)':
oddeven.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b.size(); i++) a[i] = b[i];
                   ~~^~~~~~~~~~
oddeven.cpp: In member function 'bigint bigint::operator+(const bigint&) const':
oddeven.cpp:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < x.a.size() || i < a.size(); i++) {
                   ~~^~~~~~~~~~~~
oddeven.cpp:85:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < x.a.size() || i < a.size(); i++) {
                                     ~~^~~~~~~~~~
oddeven.cpp:87:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < x.a.size()) b[i] += x.a[i];
        ~~^~~~~~~~~~~~
oddeven.cpp:88:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < a.size()) b[i] += a[i];
        ~~^~~~~~~~~~
oddeven.cpp: In member function 'bigint bigint::operator-(const bigint&) const':
oddeven.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < b.a.size(); i++) {
                   ~~^~~~~~~~~~~~
oddeven.cpp:102:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (i < x.a.size()) b.a[i] -= x.a[i];
        ~~^~~~~~~~~~~~
oddeven.cpp: In member function 'bigint bigint::operator*(const bigint&) const':
oddeven.cpp:117:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) for (int j = 0; j < x.a.size(); j++)
                   ~~^~~~~~~~~~
oddeven.cpp:117:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++) for (int j = 0; j < x.a.size(); j++)
                                                      ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct