Сообщений в теме: 4

[LVP]

Решить задачу Района 2008 Временной ключ (прикрепила условие и тесты). Протестировать себя самим.

[yanush]

Кстати количество битов можежет быть 36.
А так всё работает нормально.

 var time,ost:array[1..20,1..300000]of int64;
	ed:array[1..300000]of int64;
	n,k,x,y,l,r,i:int64;
function kol(x:int64):int64;
	var y:longint;
  	begin
   if x=0 then exit(0);
   if x<1 shl 18 then begin
   					if ed[x]=0 then begin
                                    	y:=x;
                                    	while y>0 do
     									begin
                                      	y:=y and (y-1);inc(ed[x]);
                                    	end;
   									end;
   					exit(ed[x]);
                  	end;
   kol:=kol(x shr 18)+kol(x and((1 shr 18)-1));
  end;
function next(l1,r1:int64):int64;
var i:int64;
  begin
   if time[kol(l1),r1]>0 then exit(time[kol(l1),r1]);
   i:=0;
   while r1<1 shl 18 do
	begin
	inc(i);r1:=r1+kol(l1)+kol(r1);
	end;
   l1:=l1+1;r1:=r1-(1 shl 18);
   time[kol(l),r]:=i;ost[kol(l),r]:=r1;
   exit(i);
  end;
  begin
	assign(input,'input.txt');reset(input);
	assign(output,'output.txt');rewrite(output);
	readln(n,k);
	i:=0;l:=n shr 18;r:=n and ((1 shl 18)-1);
 	while(r<1 shl 18)and(i<k)do
   	begin
        r:=r+kol(l)+kol(r);;
        inc(i);
       end;
 	if i=k then begin writeln((l shl 18)+r);exit;end;
 	l:=l+1;r:=r-(1 shl 18);
 	while i<k do
  	begin
        x:=next(l,r);
        if i+x<k then begin i:=i+x;r:=ost[kol(l),r];l:=l+1;continue;end;
        while(i<k)do
 		begin  r:=r+kol(l)+kol(r);;inc(i);end;
   	end;
 	writeln((l shl 18)+r);
  end.

[kodosov]

var wrem,ost:array[1..20,1..300000] of int64;
f:array[1..300000] of int64;
n,l,r,i,ans,k:int64;
function ked(x:int64):int64;
var i:longint;
begin
if x=0 then ked:=0
else if x>=1 shl 18 then ked:=ked(x shr 18)+ked(x and((1 shr 18)-1))
else
if f[x]>0 then ked:=f[x]
else begin
i:=x;
while i>0 do
begin
f[x]:=f[x]+1;
i:=i and(i-1);
end;
ked:=f[x];
end;
end;
function time(l,r:int64):int64;
var i:longint;
begin
i:=r;
if (wrem[ked(l),r]<>0) then time:=wrem[ked(l),r]
else begin
while r<(1 shl 18) do
begin
r:=r+ked(l)+ked®;
inc(wrem[ked(l),i]);
end;
time:=wrem[ked(l),i];
r:=r-(1 shl 18);

ost[ked(l),i]:=r;
end;
end;

begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n,k);
l:=n shr 18;
r:=n and ((1 shl 18)-1);
i:=0;
while r<(1 shl 18) do
begin

r:=r+ked(l)+ked®;
inc(i);
if i=k then break;
end;
if i<k then begin
inc(l);
r:=r-(1 shl 18);
while (i+time(l,r))<k do
begin
i:=i+time(l,r);

r:=ost[ked(l),r];
inc(l);
end;
if i<k then
while r<(1 shl 18) do
begin
r:=r+ked(l)+ked®;
inc(i);
if i=k then break;
end;
end;
ans:=l*(1 shl 18)+r;
writeln(ans);
end.

[petuhovskiy]

Все работает

var n,r,i,k : longint; numberOf1 : array [0..300000] of longint; l : int64;
	ostr,kol : array [0..300000,0..60] of longint;
function no1 (x : longint) : longint;
var j : longint;
begin
  if x=0 then exit(0);
  if x>1 shl 18 then no1:=no1(x shr 18)+no1(x and ((1 shl 18)-1)) else
  begin
	if numberOf1[x]>0 then exit(numberOf1[x]);
	j:=x;
	while j>0 do
	begin
  	j:=j and (j-1);
  	numberOf1[x]:=numberOf1[x]+1;
	end;
	no1:=numberOf1[x];
  end;
end;
function wrem (x,y : longint) : longint;
var i : longint;
begin
  if kol[y,x]>0 then exit(kol[y,x]);
  i:=y;
  while i<1 shl 18 do
  begin
	kol[y,x]:=kol[y,x]+1;
	i:=i+no1(i)+x;
	{if kol[i,x]>0 then
	begin
  	kol[y,x]:=kol[y,x]+kol[i,x];
  	ostr[y,x]:=ostr[i,x];
  	exit(kol[y,x]);
	end;  }
  end;
  ostr[y,x]:=i-(1 shl 18);
  wrem:=kol[y,x];
end;
begin
// assign(input, 'input.txt'); reset(input);
// assign(output, 'output.txt'); rewrite(output);
  readln(n,k);
  r:=n and ((1 shl 18)-1);
  l:=n shr 18;
  i:=0;
  while R<1 shl 18 do
  begin
	r:=r+no1(l)+no1(r);
	i:=i+1;
	if i=k then break;
  end;
  if i=k then begin writeln((l shl 18) + r); halt; end;
  l:=l+1;
  r:=r-(1 shl 18);
  while (i+wrem(no1(l),r))<=k do
  begin
	i:=i+wrem(no1(l),r);
	r:=ostr[r,no1(l)];
	l:=l+1;
  end;
  if i<k then
  begin
	while i<k do
	begin
  	r:=r+no1(l)+no1(r);
  	i:=i+1;
	end;
  end;
  writeln((l shl 18)+r);
end.

[Илья М.]

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

#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(r) + 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;
}