#include <iostream> #include <utility> #define mp make_pair #define F first #define S second typedef long long ll; using namespace std; const int border = 1 << 18; int n, k, r; ll l; int q[500000]; pair <int, int> t[50][270000]; int cnt(ll x) { if (x == 0) return 0; if (x > border) return cnt(x >> 18) + cnt(x & (border - 1)); if (q[x] > 0) return q[x]; int k = 0; ll n = x; while (n > 0) { k++; n = n & (n - 1); if (q[n] > 0) { k += q[n]; break; } } q[x] = k; return k; } int main() { cin.sync_with_stdio(false); cout.sync_with_stdio(false); cin >> n >> k; r = n & (border - 1); l = n >> 18; int i = 0, j = 0, x = 0; while (i < k) { int temp = cnt(l); if (t[temp][r].F > 0) { if (i + t[temp][r].F < k) { i += t[temp][r].F; r = t[temp][r].S; ++l; j = 0; x = r; continue; } } r += cnt® + temp; ++j; ++i; if (r > border) { t[temp][x].F = j; t[temp][x].S = r - border; r = r - border; ++l; j = 0; x = r; } } cout << (l << 18) + r; return 0; }
Публикации Илья М.
5 публикаций создано Илья М. (учитываются публикации только с 05-мая 23)