Sponsors

Codeforces Round #419 (Div. 1), problem: (E) Karen and Neighborhood Solution In C/C++

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

typedef pair<long long,long long> ii;

long long n,k,i,w,res;
long long m[65];
map <long long,long long> num,f,c;

long long get(long long t) {
if (f[t]>=0) return f[t];
f[t]=get((t-1)/2)+get(t/2);
if (c[t]==1) f[t]++;
return f[t];
}

void cal(long long t) {
if (c[t]==1) k–;
if (k==0) {
res+=(t-1)/2+1;
return;
}

if (f[(t-1)/2]>=k) cal((t-1)/2);
else {
res+=t-(t/2);
k-=f[(t-1)/2];
cal(t/2);
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen(“815E.inp”,”r”,stdin);
freopen(“815E.out”,”w”,stdout);
#endif // ONLINE_JUDGE

scanf(“%lld %lld”,&n,&k);

if (k==1) {
printf(“1”);
return 0;
}
if (k==2) {
printf(“%lld”,n);
return 0;
}

k-=2; n-=2;

for (i=1;i<=60;i++) {
if (i==1) {
m[1]=n;
num[n]=1;
}
else {
m[i]=(m[i-1]-1)/2;
num[m[i]]+=num[m[i-1]];
num[m[i-1]/2]+=num[m[i-1]]+num[m[i-1]+1];
num[m[i]+1]+=num[m[i-1]+1];
}
f[m[i]]=-1; f[m[i]+1]=-1;
if (m[i]==0) break;
}
num[0]=0;
num[1]+=num[2];
num[2]=0;

for (i=1;i<=60;i++) {
if (k<=num[m[i]]+num[m[i]+1]) {
if (m[i]%2==1) {
c[m[i]]=1;
c[m[i]+1]=1;
}
else {
if (k<=num[m[i]+1]) c[m[i]+1]=1;
else c[m[i]]=1,k-=num[m[i]+1];
}
break;
}
else k-=num[m[i]]+num[m[i]+1];
}
if (c[1]==1) c[2]=1;
f[0]=0;
get(n);
cal(n);
printf(“%lld”,res+1);
}

One Piece: Pirate Warriors...

One Piece: Pirate Warriors 4 Sails onto PS5 and...

Blue Origin Will Increase...

Blue Origin Supercharges New Glenn Rocket with Major Thrust...

CNBC Daily Open: Nvidia...

Nvidia CEO Jensen Huang Dismisses AI 'Bubble' Fears Amid...

How Xiaomi’s AI Efforts...

Xiaomi’s AI Leap: Powering the Next Era of the...

When Gratitude Is Weaponized:...

The Dark Side of Thankfulness: Understanding Weaponized Gratitude Gratitude is...

The Road Wraps Up...

"The Road" Hits a Major Milestone: Wrapping Up the...

One Piece: Pirate Warriors 4 Sets Sail on New-Gen Platforms, Available Now

One Piece: Pirate Warriors 4 Sails onto PS5 and Xbox Series X|S with Enhanced Features IRVINE, Calif. – Get ready to experience the epic saga...

Blue Origin Will Increase New Glenn Thrust 15-25% and Make Rocket Bigger

Blue Origin Supercharges New Glenn Rocket with Major Thrust and Size Upgrades The race for commercial space dominance just got a significant boost. Blue Origin,...

CNBC Daily Open: Nvidia CEO suggests AI doesn’t look like a bubble

Nvidia CEO Jensen Huang Dismisses AI 'Bubble' Fears Amid Massive Earnings The skyrocketing valuation of the artificial intelligence sector has led many market analysts to...

How Xiaomi’s AI Efforts Are Powering the Next Era of the Internet Ecosystem

Xiaomi’s AI Leap: Powering the Next Era of the Internet Ecosystem Artificial Intelligence (AI) has transcended its status as merely emerging technology; it is now...

When Gratitude Is Weaponized: 5 Questions for Discernment

The Dark Side of Thankfulness: Understanding Weaponized Gratitude Gratitude is often touted as a cornerstone of mental health and positive psychology. However, like any powerful...

The Road Wraps Up Its Oklahoma Ranch, OKC Run: Our S01E05 Preview

"The Road" Hits a Major Milestone: Wrapping Up the Oklahoma Leg in S01E05 Music competition fans are gearing up for the next stage of the...

A Radical New Kind of Particle Accelerator Could Transform Science

The Tabletop Revolution: Compact Particle Accelerators Poised to Transform Research For decades, the realm of high-energy physics and advanced materials science has been dominated by...

Why Native American Heritage Month matters in San Diego

The Profound Significance of Native American Heritage Month in San Diego November marks Native American Heritage Month (NAHM), a period dedicated to recognizing the rich...

Driverless rideshare service Waymo coming to San Diego gets mixed reactions

Waymo’s Driverless Rideshare Service Headed to San Diego Amid Mixed Community Reactions San Diego is officially slated to become the next major metropolitan area to...