#834907 (C++14) No.1286 Stone Skipping

提出ソース

結果

問題	No.1286 Stone Skipping
ユーザー	ecottea
提出日時	2023-01-22 04:27:57
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	7,030 bytes
コンパイル時間	3,697 ms
コンパイル使用メモリ	227,016 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-06 14:28:32
合計ジャッジ時間	4,844 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	2 ms 4,380 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	AC	1 ms 4,380 KB
testcase_10	AC	1 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	2 ms 4,380 KB
testcase_13	AC	1 ms 4,380 KB
testcase_14	AC	2 ms 4,376 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	1 ms 4,380 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	1 ms 4,380 KB
testcase_22	AC	2 ms 4,380 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	1 ms 4,376 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	1 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; // -2^63 ～ 2^63 = 9 * 10^18（int は -2^31 ～ 2^31 = 2 * 10^9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
const vi DX = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004004004004004LL;
double EPS = 1e-12;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了

// 汎用関数の定義
template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

// 手元環境（Visual Studio）
#ifdef _MSC_VER
#include "local.hpp"
// 提出用（gcc）
#else
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define gcd __gcd
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define dump_list2D(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

//using mint = modint1000000007;
using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);

istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
#endif


ll TLE(ll d) {
	for (ll x0 = d / 2; ; x0++) {
		ll x = x0, sum = 0;
		while (x > 0) {
			sum += x;
			if (sum == d) return(x0);
			if (sum > d) break;
			x /= 2;
		}
	}

	return -1;
}


void zikken() {
	repi(d, 1, (1 << 30) - 1) {
		ll res = TLE(d);

//		dump(d, bitset<16>(d), res, bitset<16>(res), res - d / 2);

		if (res == d) {
			dump(bitset<30>(d), d);
		}
	}
	exit(0);
}
/*
000000000000000000000000000001 1
000000000000000000000000000010 2
000000000000000000000000000101 5
000000000000000000000000010100 20
000000000000000000000000101100 44
000000000000000000000001101011 107
000000000000000000000101111001 377
000000000000000000000110111000 440
000000000000000000001001111000 632
000000000000000000001110110000 944
000000000000000000011011111000 1784
000000000000000000111100101111 3887
000000000000000000111101101110 3950
000000000000000001111011010111 7895
000000000000000110101001001111 27215
000000000000001101111001001101 56909
000000000000001110000001101111 57455
000000000000111001110101100100 236900
000000000001110001100101101100 465260
000000000010101010011111110101 698357
000000000011100000101000110101 920117
000000000011100001101000110100 924212
000000000011111110001011110001 1041137
000000000011111110001111110011 1041395
000000000011111111011011100000 1046240
000000000111100000100001110101 1968245
000000000111111111011011011111 2094815
000000000111111111011111101101 2095085
000000001111010100101100110001 4016945
000000001111011010010000110010 4039730
000000001111101101011100101000 4118312
000000001111111100010111110000 4179440
000000011010101111011001001001 7009865
000000011111111011111100101100 8372012
000000011111111011111101101011 8372075
000000111000000110100000110100 14706740
000000111111100001001001101001 16650857
000001011111111011111101101010 25149290
000001110000001101000001101100 29413484
000001111111111011011110100011 33535907
000001111111111011111011011011 33537755
000011100000000000000001101111 58720367
000011100000001101011100110001 58775345
000011111111111011111001011011 67092059
000110110011000001111011001000 114040520
...
*/


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");

//	zikken();

	ll d;
	cin >> d;

	// i : 進む回数
	repir(i, 61, 1) {
		ll ini = (1LL << 61) - (1LL << (61 - i));
		dump(bitset<61>(ini));

		ll res = 0, x = d;
		rep(j, 61) {
			ll del = ini >> j;
			if (x >= del) {
				x -= del;
				res += 1LL << (60 - j);
			}
		}

		if (x == 0) EXIT(res);
	}
}

yukicoder

結果

テストケース

ソースコード