結果
問題 | No.2426 Select Plus or Minus |
ユーザー |
|
提出日時 | 2023-08-18 21:18:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 6,722 bytes |
コンパイル時間 | 1,977 ms |
コンパイル使用メモリ | 202,652 KB |
最終ジャッジ日時 | 2025-02-16 09:26:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#ifndef hari64#include <bits/stdc++.h>// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#define debug(...)#else#include "util/viewer.hpp"#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)#endif// clang-format offusing namespace std;template <typename T> using vc = vector<T>;template <typename T> using vvc = vector<vc<T>>;template <typename T> using vvvc = vector<vvc<T>>;using ll = long long; using ld = long double;using pii = pair<int, int>; using pll = pair<ll, ll>;using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;using vll = vc<ll>; using vvll = vvc<ll>; using vvvll = vvvc<ll>;using vb = vc<bool>; using vvb = vvc<bool>; using vvvb = vvvc<bool>;using vpii = vc<pii>; using vvpii = vvc<pii>; using vpll = vc<pll>; using vvpll = vvc<pll>;using vtiii = vc<tiii>; using vvtiii = vvc<tiii>; using vtlll = vc<tlll>; using vvtlll = vvc<tlll>;#define ALL(x) begin(x), end(x)#define RALL(x) (x).rbegin(), (x).rend()constexpr int INF = 1001001001; constexpr long long INFll = 1001001001001001001;template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }// clang-format onstruct Xor128 { // period 2^128 - 1uint32_t x, y, z, w;static constexpr uint32_t min() { return 0; }static constexpr uint32_t max() { return UINT32_MAX; }Xor128(uint32_t seed = 0): x(123456789), y(362436069), z(521288629), w(88675123 + seed) {}uint32_t operator()() {uint32_t t = x ^ (x << 11);x = y;y = z;z = w;return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));}uint32_t operator()(uint32_t l, uint32_t r) { return ((*this)() % (r - l)) + l; }uint32_t operator()(uint32_t r) { return (*this)() % r; }};struct Rand { // https://docs.python.org/ja/3/library/random.htmlRand(){};Rand(int seed) : gen(seed){};// シードを変更しますinline void set_seed(int seed) {Xor128 _gen(seed);gen = _gen;}// ランダムな浮動小数点数(範囲は[0.0, 1.0)) を返しますinline double random() { return (double)gen() / (double)gen.max(); }// a <= b であれば a <= N <= b 、b < a であれば b <= N <= a// であるようなランダムな浮動小数点数 N を返しますinline double uniform(double a, double b) {if (b < a) swap(a, b);return a + (b - a) * double(gen()) / double(gen.max());}// range(0, stop) の要素からランダムに選ばれた要素を返しますinline uint32_t randrange(uint32_t r) { return gen(r); }// range(start, stop) の要素からランダムに選ばれた要素を返しますinline uint32_t randrange(uint32_t l, uint32_t r) { return gen(l, r); }// a <= N <= b であるようなランダムな整数 N を返します randrange(a, b + 1)// のエイリアスですinline uint32_t randint(uint32_t l, uint32_t r) { return gen(l, r + 1); }// シーケンス x をインプレースにシャッフルしますtemplate <class T>void shuffle(vector<T>& x) {for (int i = x.size(), j; i > 1;) {j = gen(i);swap(x[j], x[--i]);}}// 空でないシーケンス seq からランダムに要素を返しますtemplate <class T>T choice(const vector<T>& seq) {assert(!seq.empty());return seq[gen(seq.size())];}// 相対的な重みに基づいて要素が選ばれます (※複数回呼ぶ場合は処理を変えた方が良い)template <class T, class U>T choice(const vector<T>& seq, const vector<U>& weights) {assert(seq.size() == weights.size());vector<U> acc(weights.size());acc[0] = weights[0];for (int i = 1; i < int(weights.size()); i++) acc[i] = acc[i - 1] + weights[i];return seq[lower_bound(acc.begin(), acc.end(), random() * acc.back()) -acc.begin()];}// 母集団のシーケンスまたは集合から選ばれた長さ k// の一意な要素からなるリストを返します 重複無しのランダムサンプリングに用いられますtemplate <class T>vector<T> sample(const vector<T>& p, int k) {int j, i = 0, n = p.size();assert(0 <= k && k <= n);vector<T> ret(k);unordered_set<int> s;for (; i < k; i++) {do {j = gen(n);} while (s.find(j) != s.end());s.insert(j);ret[i] = p[j];}return ret;}// 正規分布です mu は平均で sigma は標準偏差ですdouble normalvariate(double mu = 0.0, double sigma = 1.0) {double u2, z, NV = 4 * exp(-0.5) / sqrt(2.0);while (true) {u2 = 1.0 - random();z = NV * (random() - 0.5) / u2;if (z * z / 4.0 <= -log(u2)) break;}return mu + z * sigma;}private:Xor128 gen;} myrand;int main() {cin.tie(0);ios::sync_with_stdio(false);ll N;cin >> N;while (true) {set<ll> seen;vc<char> path;vc<char> ans;auto dfs = [&](const auto& f, ll x) -> void {debug(x);if (!ans.empty()) return;if (seen.count(x)) return;if (x == 1) {ans = path;return;}seen.insert(x);if (x % 2 == 0) {path.push_back('/');f(f, x / 2);path.pop_back();} else {if (x < (ll)1e18 / 3) {if (myrand.random() < 0.5) {path.push_back('+');f(f, 3 * x + 1);path.pop_back();path.push_back('-');f(f, 3 * x - 1);path.pop_back();} else {path.push_back('-');f(f, 3 * x - 1);path.pop_back();path.push_back('+');f(f, 3 * x + 1);path.pop_back();}}}};dfs(dfs, N);if (int(path.size()) < 10000) {cout << ans.size() << endl;for (auto& elem : ans) cout << elem << ' ';cout << endl;return 0;}}return 0;}