aryamanarora / competitive-programming Goto Github PK

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
 
#define mp make_pair
#define pb push_back
#define f first
#define s second

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    bitset<64> a(n);
    if (a.count() == k) {
        string s = a.to_string();
        next_permutation(s.begin(), s.end());
        cout << stoull(s, nullptr, 2) << endl;
        return 0;
    }
    while (a.count() != k) {
        if (a.count() > k) {
            int ct = 0, i;
            for (i = 0; i < 64; i++) {
                if (a[i]) {
                    ct++;
                    a[i] = false;
                    if (ct == 2) break;
                }
            }
            i++;
            while (a[i]) {
                a[i] = false;
                i++;
            }
            a[i] = true;
        }
        else {
            for (int i = 0; i < 64; i++) {
                if (!a[i]) {
                    a[i] = true;
                    break;
                }
            }
        }
    }
    cout << a.to_ullong() << endl; 
}

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;

typedef set<int> si;
typedef set<ii> sii;
typedef set<ld> sd;
typedef set<ll> sl;

typedef map<int, int> mii;
typedef priority_queue<int> pqi;
typedef queue<int> qi;
 
#define mp make_pair
#define pb push_back
#define f first
#define s second

mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
T least_significant_one(T x) {
    return (x & (-x));
}

struct fenwick_tree {
    int n;
    vl freq;
    fenwick_tree(int N) : n(N), freq(N + 1, 0) {};
    ll sum(int a) {
        ll res = 0;
        for (; a; a -= least_significant_one(a)) res += freq[a];
        return res;
    }
    void add(int a, int v) {
        for (; a <= n; a += least_significant_one(a)) freq[a] += v;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;
    vi a(n); for (auto &x : a) cin >> x;
    
    // compression
    si a_compress; for (auto &x : a) a_compress.insert(x);
    mii key, rkey;
    int ct = 1;
    for (auto &x : a_compress) {
        key[x] = ct;
        rkey[ct] = x;
        ct++;
    }
    
    fenwick_tree ct(a_compress.size() + 5), sum(a_compress.size() + 5);
    for (int i = 0; i < k - 1; i++) {
        ct.add(key[a[i]], 1);
        sum.add(key[a[i]], a[i]);
    }
    
    
}

/*
USE LONG LONG!!!!

:pray: :fishy15:
:pray: :summitosity:
:pray: :prodakcin:

          .=     ,        =.
  _  _   /'/    )\,/,/(_   \ \
   `//-.|  (  ,\\)\//\)\/_  ) |
   //___\   `\\\/\\/\/\\///'  /
,-"~`-._ `"--'_   `"""`  _ \`'"~-,_
\       `-.  '_`.      .'_` \ ,-"~`/
 `.__.-'`/   (-\        /-) |-.__,'
   ||   |     \O)  /^\ (O/  | .        <-  BESSIE THE COW
   `\\  |         /   `\    /
     \\  \       /      `\ /
      `\\ `-.  /' .---.--.\
        `\\/`~(, '()      ('
         /(O) \\   _,.-.,_)    
        //  \\ `\'`      /
       / |  ||   `""""~"`
     /'  |__||
           `o
*/