Submission #1263729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263729		proofy	Odd-even (IZhO11_oddeven)	C++20	0 / 100	2093 ms	328 KiB

oddeven

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

void print(__int128 x) {
	string t;
	while (x > 0) {
		t.push_back((x % 10) + '0');
		x /= 10;
	}
	reverse(t.begin(), t.end());
	cout << t << "\n";
}

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

	__int128 a = 0;
	for (char c : x) {
		a *= 10;
		a += c - '0';
	}

	auto f = [&](__int128 x) {
		return (x * (x + 1)) / 2;
	};

	__int128 l = 0, r = 1;
	while (f(r) <= a) r <<= 1;

	while (r - l > 1) {
		__int128 mid = (l + r) / 2;
		if (f(mid) <= a) l = mid;
		else r = mid;
	}
	__int128 y = l;
	
	if ((y * (y + 1)) / 2 == a) {
		print(y * y);
	} else {
		__int128 k = a - ((y * (y + 1)) / 2);
		print(y * y + 2 * k - 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: 0 / 100