#334208 (C++14) No.8055 2019（注：異常な難易度です）

• 問題: No.8055 2019（注：異常な難易度です）
• ユーザー: risujiroh
• 提出日時: 2019-04-01 23:41:09
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: MLE
• 実行時間: -
• コード長: 9,194 bytes
• コンパイル時間: 2,495 ms
• コンパイル使用メモリ: 200,684 KB
• 実行使用メモリ: 814,788 KB
• 最終ジャッジ日時: 2024-11-27 05:08:58
• 合計ジャッジ時間: 20,221 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
other	AC * 82 MLE * 9

ソースコード

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

template<unsigned P> struct ModInt {
  using M = ModInt;
  unsigned v;
  ModInt() : v(0) {}
  template<class Z> ModInt(Z x) : v(x >= 0 ? x % P : (P - -x % P) % P) {}
  constexpr ModInt(unsigned v, int) : v(v) {}
  static constexpr unsigned p() { return P; }
  M operator+() const { return *this; }
  M operator-() const { return {v ? P - v : 0, 0}; }
  explicit operator bool() const noexcept { return v; }
  bool operator!() const noexcept { return !(bool) *this; }
  M operator*(M r) const { return M(*this) *= r; }
  M operator/(M r) const { return M(*this) /= r; }
  M operator+(M r) const { return M(*this) += r; }
  M operator-(M r) const { return M(*this) -= r; }
  bool operator==(M r) const { return v == r.v; }
  bool operator!=(M r) const { return !(*this == r); }
  M& operator*=(M r) { v = (uint64_t) v * r.v % P; return *this; }
  M& operator/=(M r) { return *this *= r.inv(); }
  M& operator+=(M r) { if ((v += r.v) >= P) v -= P; return *this; }
  M& operator-=(M r) { if ((v += P - r.v) >= P) v -= P; return *this; }
  M inv() const {
    int a = v, b = P, x = 1, u = 0;
    while (b) {
      int q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * u, u);
    }
    assert(a == 1);
    return x;
  }
  template<class Z> M pow(Z n) const {
    if (n < 0) return pow(-n).inv();
    M res = 1;
    for (M a = *this; n; a *= a, n >>= 1) if (n & 1) res *= a;
    return res;
  }
  template<class Z> friend M operator*(Z l, M r) { return M(l) *= r; }
  template<class Z> friend M operator/(Z l, M r) { return M(l) /= r; }
  template<class Z> friend M operator+(Z l, M r) { return M(l) += r; }
  template<class Z> friend M operator-(Z l, M r) { return M(l) -= r; }
  friend ostream& operator<<(ostream& os, M r) { return os << r.v; }
  friend istream& operator>>(istream& is, M& r) { lint x; is >> x; r = x; return is; }
  template<class Z> friend bool operator==(Z l, M r) { return M(l) == r; }
  template<class Z> friend bool operator!=(Z l, M r) { return !(l == r); }
};
template<unsigned P, unsigned g> void ntt(V< ModInt<P> >& a, bool inv = false) {
  int n = a.size();
  int j = 0;
  for (int i = 1; i < n; ++i) {
    int k = n >> 1;
    while (j >= k) j -= k, k >>= 1;
    j += k;
    if (i < j) swap(a[i], a[j]);
  }
  assert((P - 1) % n == 0);
  auto xi = ModInt<P>(g).pow((P - 1) / n);
  if (inv) xi = xi.inv();
  for (int k = 1; k < n; k <<= 1) {
    ModInt<P> dt = xi.pow((n >> 1) / k);
    for (int i0 = 0; i0 < n; i0 += k << 1) {
      ModInt<P> t = 1;
      for (int i = i0; i < i0 + k; ++i) {
        j = i + k;
        a[j] *= t, t *= dt;
        tie(a[i], a[j]) = make_pair(a[i] + a[j], a[i] - a[j]);
      }
    }
  }
}
template<unsigned P, unsigned g = 6420> void multiply(V< ModInt<P> >& a, V< ModInt<P> >& b) {
  assert(!a.empty() and !b.empty());
  int n = 1 << __lg(2 * (a.size() + b.size() - 1) - 1);
  a.resize(n), b.resize(n);
  ntt<P, g>(a), ntt<P, g>(b);
  for (int i = 0; i < n; ++i) a[i] *= b[i];
  ntt<P, g>(a, true);
  auto inv_n = ModInt<P>(n).inv();
  for (int i = 0; i < n; ++i) a[i] *= inv_n;
}
void multiply(V<lint>& a, const V<lint>& b) {
  using Mint0 = ModInt<1811939329>;
  using Mint1 = ModInt<2013265921>;
  int n = a.size(), m = b.size();
  V<Mint0> a0(n), b0(m);
  V<Mint1> a1(n), b1(m);
  for (int i = 0; i < n; ++i) a0[i] = a[i], a1[i] = a[i];
  for (int j = 0; j < m; ++j) b0[j] = b[j], b1[j] = b[j];
  multiply(a0, b0);
  multiply(a1, b1);
  n = a0.size();
  a.resize(n);
  auto inv = Mint1(Mint0::p()).inv();
  for (int i = 0; i < n; ++i) {
    a[i] = a0[i].v + (lint) Mint0::p() * ((a1[i] - a0[i].v) * inv).v;
  }
}
struct Bint {
  bool neg;
  string s;
  Bint() : neg(false), s("0") {}
  Bint(const string& x) : neg(x[0] == '-'), s(x.substr(neg)) {}
  Bint(lint x) : neg(x < 0), s(to_string(abs(x))) {}
  Bint(bool neg, const string& s) : neg(neg), s(s) {}
  Bint operator+() const { return *this; }
  Bint operator-() const { return {!neg, s}; }
  explicit operator bool() const noexcept { return s != "0"; }
  bool operator!() const noexcept { return !(bool) *this; }
  Bint operator*(const Bint& r) const { return Bint(*this) *= r; }
  Bint operator/(const Bint& r) const { return Bint(*this) /= r; }
  Bint operator%(const Bint& r) const { return Bint(*this) %= r; }
  Bint operator+(const Bint& r) const { return Bint(*this) += r; }
  Bint operator-(const Bint& r) const { return Bint(*this) -= r; }
  bool operator<(const Bint& r) const {
    if (neg != r.neg) return neg;
    return neg ^ (s.size() != r.s.size() ? s.size() < r.s.size() : s < r.s);
  }
  bool operator>(const Bint& r) const { return r < *this; }
  bool operator<=(const Bint& r) const { return !(*this > r); }
  bool operator>=(const Bint& r) const { return !(*this < r); }
  bool operator==(const Bint& r) const { return neg == r.neg and s == r.s; }
  bool operator!=(const Bint& r) const { return !(*this == r); }
  Bint& operator*=(const Bint& r) {
    if (!*this or !r) {
      neg = false, s = "0";
      return *this;
    }
    neg ^= r.neg;
    auto t = r.s;
    if (s.size() + t.size() < 20) {
      s = to_string(stoull(s) * stoull(t));
      return *this;
    }
    constexpr int D = 6;
    constexpr int B = 1e6;
    V<lint> a;
    for (int i = s.size(); i > 0; i -= D) {
      a.push_back(stoi(s.substr(max(i - D, 0), min(D, i))));
    }
    V<lint> b;
    for (int i = t.size(); i > 0; i -= D) {
      b.push_back(stoi(t.substr(max(i - D, 0), min(D, i))));
    }
    multiply(a, b);
    V<> res;
    lint c = 0;
    for (int i = 0; i < (int) a.size(); ++i) {
      res.push_back((c += a[i]) % B);
      c /= B;
    }
    s = to_string(c);
    while (!res.empty()) {
      auto t = to_string(res.back());
      while (t.size() < D) t = '0' + t;
      s += t;
      res.pop_back();
    }
    int i = 0;
    while (i < (int) s.size() and s[i] == '0') ++i;
    s = s.substr(i);
    return *this;
  }
  Bint& operator/=(const Bint& r) {
    assert(r);
    auto t = r.s;
    if (Bint(s) < Bint(t)) {
      neg = false, s = "0";
      return *this;
    }
    neg ^= r.neg;
    string res;
    for (int i = s.size() - t.size(); i >= 0; --i) {
      char c = '0';
      while (Bint(s) >= Bint(t + string(i, '0'))) {
        s = (Bint(s) - Bint(t + string(i, '0'))).s;
        ++c;
      }
      res += c;
    }
    s = res;
    int i = 0;
    while (i < (int) s.size() and s[i] == '0') ++i;
    s = s.substr(i);
    return *this;
  }
  Bint& operator%=(const Bint& r) { return *this -= *this / r * r; }
  Bint& operator+=(const Bint& r) {
    auto t = r.s;
    reverse(begin(s), end(s));
    reverse(begin(t), end(t));
    while (s.size() < t.size()) s += '0';
    while (t.size() < s.size()) t += '0';
    s += '0', t += '0';
    if (neg == r.neg) {
      int c = 0;
      for (int i = 0; i < (int) s.size(); ++i) {
        if ((s[i] += t[i] - '0' + c) > '9') {
          s[i] -= 10;
          c = 1;
        } else c = 0;
      }
    } else {
      if (neg) swap(s, t);
      s.back() = '1';
      int c = 0;
      for (int i = 0; i < (int) s.size(); ++i) {
        if ((s[i] -= t[i] - '0' + c) < '0') {
          s[i] += 10;
          c = 1;
        } else c = 0;
      }
      if (neg = s.back() == '0') {
        int i = 0;
        while (s[i] == '0') ++i;
        s[i] = '0' + 10 - (s[i] - '0');
        while (++i < (int) s.size() - 1) s[i] = '9' - (s[i] - '0');
      } else s.back() = '0';
    }
    while (s.size() > 1 and s.back() == '0') s.pop_back();
    reverse(begin(s), end(s));
    return *this;
  }
  Bint& operator-=(const Bint& r) { return *this += -r; }
  template<class Z> friend Bint operator*(Z l, const Bint& r) { return Bint(l) *= r; }
  template<class Z> friend Bint operator/(Z l, const Bint& r) { return Bint(l) /= r; }
  template<class Z> friend Bint operator%(Z l, const Bint& r) { return Bint(l) %= r; }
  template<class Z> friend Bint operator+(Z l, const Bint& r) { return Bint(l) += r; }
  template<class Z> friend Bint operator-(Z l, const Bint& r) { return Bint(l) -= r; }
  friend ostream& operator<<(ostream& os, const Bint& r) { if (r.neg) os << '-'; return os << r.s; }
  friend istream& operator>>(istream& is, Bint& r) { string x; is >> x; r = x; return is; }
  template<class Z> friend bool operator==(Z l, const Bint& r) { return Bint(l) == r; }
  template<class Z> friend bool operator!=(Z l, const Bint& r) { return !(l == r); }
};

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  int k = 1, s = 0;
  while (true) {
    s += (k - 1) * (k - 2) / 2 + 1;
    if (n <= s) break;
    ++k;
  }
  s -= (k - 1) * (k - 2) / 2 + 1;
  n -= s + 1;
  V<string> a;
  a.push_back(string(k, '1'));
  for (int x = 1; x <= k - 2; ++x) for (int z = 1; z <= k - 2; ++z) {
    int y = k - x - z;
    if (y <= 0) continue;
    auto s = string(x, '1') + string(y, '0') + string(z, '1');
    a.push_back(s);
  }
  sort(begin(a), end(a));
  auto str = a[n];
  reverse(begin(str), end(str));
  Bint res, x = 1;
  for (int i = 0; i < k; ++i) {
    if (str[i] == '1') {
      res += x;
    }
    x += x;
  }
  cout << res << '\n';
}