luchobazz / cpp-algorithm-snippets Goto Github PK

struct SegmTree {
  vector<int> T; int n;
  SegmTree(int n) : T(2 * n, (int)-2e9), n(n) {}
  
  void Update(int pos, int val) {
    for (T[pos += n] = val; pos > 1; pos /= 2)
      T[pos / 2] = max(T[pos], T[pos ^ 1]);
  }
  
  int Query(int b, int e) {
    int res = -2e9;
    for (b += n, e += n; b < e; b /= 2, e /= 2) {
      if (b % 2) res = max(res, T[b++]);
      if (e % 2) res = max(res, T[--e]);
    }
    return res;
  }
};

template <typename Monoid>
struct FenwickTree {
  using G = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;
  E total;
 
  FenwickTree() {}
  FenwickTree(int n) { build(n); }
  template <typename F>
  FenwickTree(int n, F f) {
    build(n, f);
  }
  FenwickTree(const vc<E>& v) { build(v); }
 
  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
    total = G::unit();
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.clear();
    dat.reserve(n);
    total = G::unit();
    FOR(i, n) { dat.eb(f(i)); }
    for (int i = 1; i <= n; ++i) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
    }
    total = prefix_sum(m);
  }
 
  E prod_all() { return total; }
  E sum_all() { return total; }
  E sum(int k) { return prefix_sum(k); }
  E prod(int k) { return prefix_prod(k); }
  E prefix_sum(int k) { return prefix_prod(k); }
  E prefix_prod(int k) {
    chmin(k, n);
    E ret = G::unit();
    for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
    return ret;
  }
  E sum(int L, int R) { return prod(L, R); }
  E prod(int L, int R) {
    chmax(L, 0), chmin(R, n);
    if (L == 0) return prefix_prod(R);
    assert(0 <= L && L <= R && R <= n);
    E pos = G::unit(), neg = G::unit();
    while (L < R) { pos = G::op(pos, dat[R - 1]), R -= R & -R; }
    while (R < L) { neg = G::op(neg, dat[L - 1]), L -= L & -L; }
    return G::op(pos, G::inverse(neg));
  }
 
  void add(int k, E x) { multiply(k, x); }
  void multiply(int k, E x) {
    static_assert(G::commute);
    total = G::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
  }
 
  template <class F>
  int max_right(const F check) {
    assert(check(G::unit()));
    int i = 0;
    E s = G::unit();
    int k = 1;
    while (2 * k <= n) k *= 2;
    while (k) {
      if (i + k - 1 < len(dat)) {
        E t = G::op(s, dat[i + k - 1]);
        if (check(t)) { i += k, s = t; }
      }
      k >>= 1;
    }
    return i;
  }
 
  int kth(E k) {
    return max_right([&k](E x) -> bool { return x <= k; });
  }
};

PrefixSum() n(-1) {}

PrefixSum(): n(-1) {}

const string ALPHA = "abcdefghijklmnopqrstuvwxyz";

#define _ << ' ' <<

// usage: 
cout << x _ y << endl;
// cout << x << ' ' << y << endl;

struct RMQ {
  vector<vector<int>> table;
  RMQ(vector<int> &v) : table(20, vector<int>(v.size())) {
    int n = v.size();
    for (int i = 0; i < n; i++) table[0][i] = v[i];
    for (int j = 1; (1<<j) <= n; j++)
      for (int i = 0; i + (1<<j-1) < n; i++)
        table[j][i] = max(table[j-1][i], table[j-1][i + (1<<j-1)]);
  }
  int query(int a, int b) {
    int j = 31 - __builtin_clz(b-a+1);
    return max(table[j][a], table[j][b-(1<<j)+1]);
  }
};

auto go = y_combinator([&](auto Go, int idx) -> int64 {
    // Go(idx-1);
});

int ans = go(0);

#define infinity while(1)
#define unreachable assert(false && "Unreachable");

// Reference: https://codeforces.com/contest/1782/submission/230743928
int floordiv(int a, int b) {
  return a > 0 ? a / b : -((-a + b - 1) / b);
}
 
int ceildiv(int a, int b) {
  return a > 0 ? (a + b - 1) / b : -(-a / b);
}
 

template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

const char SPECIAL_CH = '$';
const string FIRST_ALPHA = "0";
const string SECOND_ALPHA = "1";
struct HffTreeNode {
    // One of the input characters
    char ch;
    // Frequency of the character
    uint32_t freq;
    // Left and right child
    HffTreeNode *left, *right;
    HffTreeNode(char ch, uint32_t freq) {
        left = right = NULL;
        this->ch = ch;
        this->freq = freq;
    }
};

struct Code {
    char ch;
    string bin;
};

// For comparison of
// two heap nodes (needed in min heap)
struct Compare {
    bool operator()(HffTreeNode* l, HffTreeNode* r) {
        return l->freq > r->freq;
    }
};
 
// Prints huffman codes from
// the root of Huffman Tree.
void buildCodes(vector<Code> &codes, struct HffTreeNode* root, string str) {
    if (!root) return;
    if (root->ch != SPECIAL_CH) codes.push_back(Code{root->ch, str});
    buildCodes(codes, root->left, str + FIRST_ALPHA);
    buildCodes(codes, root->right, str + SECOND_ALPHA);
}
 
// The main function that builds a Huffman Tree and
// print codes by traversing the built Huffman Tree
HffTreeNode* HuffmanCodes(vector<char> alpha, vector<int> freq) {
    int size = (int) alpha.size();
    struct HffTreeNode *left, *right, *top;
    // Create a min heap & inserts all characters of alpha[]
    priority_queue<HffTreeNode*, vector<HffTreeNode*>, Compare> minHeap;
    
    for (int i = 0; i < size; ++i) {
        minHeap.push(new HffTreeNode(alpha[i], freq[i]));
    }
    #define pop_heap(heap) heap.top(); heap.pop();
    
    // Iterate while size of heap doesn't become 1
    while (minHeap.size() != 1) {
        // Extract the two minimum
        // freq items from min heap
        left = pop_heap(minHeap);
        right = pop_heap(minHeap);
        // Create a new internal node with frequency equal to the sum of the
        // two nodes frequencies. Make the two extracted node as left and right
        // children of this new node. Add this node to the min heap '$'
        // is a special value for internal nodes, not used
        top = new HffTreeNode(SPECIAL_CH, left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    return minHeap.top();
}

// Usage:
// vector<char> alpha = { 'a', 'b', 'c', 'd', 'e', 'f' };
// vector<int> freq = { 5, 9, 12, 13, 16, 45 };
// HffTreeNode* root = HuffmanCodes(alpha, freq);
// vector<Code> codes;
// buildCodes(codes, root, "");
// for(auto &code: codes) cout << code.ch << ": " << code.bin << endl;

if(dist[e.from] + e.cost < dist[e.to] && dist[e.from] != inf)

if(dist[e.from] != inf && dist[e.from] + e.cost < dist[e.to])

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

// Input: 1267650600228229401496703205376
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;
const i128 ONE_128 = i128(1);
const i128 ZERO_128 = i128(0);


std::istream &operator>>(std::istream &is, i128 &n) {
    n = 0;
    std::string s;
    is >> s;
    
    for (auto c : s) {
        n = 10 * n + c - '0';
    }
    return is;
}
 
std::ostream &operator<<(std::ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    std::string s;
    while (n > 0) {
        s += '0' + n % 10;
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}


int main() {
    
    i128 number; cin >> number;
    
    for(int i = 128-1; i >= 0; i--) {
        cout << bool(number & (ONE_128 << i));
    }
    cout << endl;
    
    cout << number << endl;
    
    return 0;   
}