Рабочий код на С++.

#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;
}

http://e-maxx.ru/upl...e-maxx_algo.pdf
Тыкаем, сохраняем, радуемся.

в процедуре поиска дуги лучше описать в варе i, ибо чаще всего без этого не пойдёт

Просьба удалить темы спамеров в разделе "Расписание олимпиад", ибо бесят.

Как убирать сообщения? о_о