제출 #1263787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263787		proofy	홀-짝 수열 (IZhO11_oddeven)	C++20	100 / 100	593 ms	440 KiB

oddeven

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int ones(int b) {
	return (1 << b) - 1;
}

// all integers have to use <= (N / 2) - 2 digits
template <int B, int N>
struct big_int {
	int a[N];
	big_int() { memset(a, 0, sizeof(a)); }
	big_int(int x) {
		memset(a, 0, sizeof(a));
		for (int i = 0; i < N && x; i++) 
			a[i] = x & ones(B), x >>= B;
	}

	big_int operator + (const big_int& o) const {
		big_int r;
		int carry = 0;
		for (int i = 0; i < N; i++) {
			int sum = a[i] + o.a[i] + carry;
			r.a[i] = sum & ones(B);
			carry = sum >> B;
		}
		return r;
	}
	
	bool operator < (const big_int& o) const {
		for (int i = N - 1; i >= 0; --i) if (a[i] != o.a[i])
			return a[i] < o.a[i];
		return false;
	}

	bool operator <= (const big_int& o) const {
		return !(o < *this);
	}

	big_int operator - (const big_int& o) const {
		big_int r;
		for (int i = 0; i < N; i++) r.a[i] = a[i] - o.a[i];

		for (int i = N - 1; i >= 0; --i) if (r.a[i] < 0) {
			for (int j = i + 1; j < N; j++) 
				if (r.a[j] == 0) r.a[j] = ones(B);
				else {
					assert(r.a[j] > 0);
					r.a[j] -= 1;
					break;
				}
			r.a[i] += (1 << B);
		}

		return r;
	}

	big_int operator * (const big_int& o) const {
		big_int r;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++) if (i + j < N)
				r.a[i + j] += a[i] * o.a[j];
		
		int carry = 0;
		for (int i = 0; i < N; i++) {
			carry += r.a[i];
			r.a[i] = carry & ones(B);
			carry >>= B;
		}
		return r;
	}

	big_int operator / (const big_int& o) const {
		if (*this < o) return big_int();
		int m = (N >> 1) - 2;
		big_int r;
		for (int i = m; i >= 0; --i) 
			for (int j = B - 1; j >= 0; --j) {
				r.a[i] ^= (1 << j);
				if ((r * o) <= *this) continue;
				r.a[i] ^= (1 << j);
			}
		return r;
	}

	big_int operator % (const big_int& o) const {
		if (*this < o) return *this;
		return *this - (o * (*this / o));
	}

	void operator = (const big_int& o) {
		for (int i = 0; i < N; i++) a[i] = o.a[i];
	}
	bool operator == (const big_int& o) const {
		for (int i = 0; i < N; i++) if (a[i] != o.a[i]) return false;
		return true;
	}

	big_int divide_2() {
		big_int r = *this;
		for (int i = 0; i < N; i++) {
			r.a[i] >>= 1;
			if (i + 1 < N) {
				if (r.a[i + 1] & 1) r.a[i] |= (1 << (B - 1));
			}
		}
		return r;
	}

	big_int multiply_2() {
		big_int r = *this;
		for (int i = N - 1; i >= 0; --i) {
			r.a[i] <<= 1;
			r.a[i] &= ones(B);
			if (i - 1 >= 0 && (r.a[i - 1] & (1 << (B - 1))) > 0) r.a[i] |= 1;
		}
		return r;
	}
};

#define bigint big_int<7, 128>

void print(bigint a) {
	bigint q(100);
	string x;
	while (bigint() < a) {
		string t = to_string((a % q).a[0]);
		reverse(t.begin(), t.end());
		while ((int)t.length() < 2) t.push_back('0');
		for (char c : t) x.push_back(c);
		a = (a / q);
	}

	while (!x.empty() && x.back() == '0') x.pop_back();
	if (x.empty()) x.push_back('0');

	reverse(x.begin(), x.end());
	cout << x << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	string x;
	cin >> x;
	
	bigint a;
	
	for (char c : x) {
		a = a * bigint(10);
		a = a + bigint(c - '0');
	}

	auto f = [&](bigint x) {
		return (x * (x + bigint(1))).divide_2();
	};

	bigint l = bigint(), r = bigint(1);
	while (f(r) <= a) r = r.multiply_2();
	while (bigint(1) < r - l) {
		bigint mid = (l + r).divide_2();
		if (f(mid) <= a) l = mid;
		else r = mid;
	}

	if (f(l) == a) {
		print(l * l);
	} else {
		bigint k = a - f(l);
		print(l * l + k.multiply_2() - 1);
	}
}

/*
$\newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}}$
$\newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}}$
$\newcommand{\prob}[1]{\Pr\paren{#1}}$
$\newcommand{\card}[1]{|#1|}$
$\newcommand{\paren}[1]{\left ( #1 \right )}$
$\newcommand{\Paren}[1]{\Big(#1\Big)}$
$\newcommand{\bracket}[1]{\left [ #1 \right ]}$
$\newcommand{\var}[1]{\textnormal{Var}\bracket{#1}}$
$\newcommand{\curly}[1]{\left\{ #1 \right\}}$
$\newcommand{\poly}{\mbox{\rm poly}}$
$\newcommand{\eps}{\varepsilon}$
$\newcommand{\inner}[2]{\langle #1\,,\,#2 \rangle}$
$\newcommand{\norm}[1]{	\lVert #1 \rVert}$
$\newcommand{\supp}[1]{\ensuremath{\textnormal{supp}}(#1)}$
$\renewcommand{\leq}{\leqslant}$
$\renewcommand{\geq}{\geqslant}$
$\newcommand{\IR}{\mathbb{R}}$
$\newcommand{\IN}{\mathbb{N}}$
$\newcommand{\backforth}{\leftrightarrow}$

We show by inducting on $n$ that the $n(n + 1)/2$ th integer in the sequence is $n^2$, and furthermore the length of the greatest suffix of the same parity ending at such an integer is $n$. 

Base case is trivial. 

Assume that $n(n - 1)/2$ th integer in the sequence is $(n - 1)^2$. If $n - 1$ is even, then we get $n$ more odd integers. In particular, they are

$$(n - 1)^2 + 1, (n - 1)^2 + 3, \dots, (n - 1)^2 + 2n-1$$

and the last integer in the sequence is $n^2$, as desired.
*/

• Subtask 1: 100 / 100