记录编号	222195	评测结果	AAAAAAAAAA
题目名称	[USACO Dec02]奶牛职业网球赛	最终得分	100
用户昵称	Pyh	是否通过	通过
代码语言	C++	运行时间	0.174 s
提交时间	2016-01-29 11:07:57	内存使用	4.00 MiB

//
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int t,k,n,l=1,r,ans=0,tot;

int fa[100000];
bool in[100000];
int num[100000];

inline int Max(int x,int y){
	return x>y?x:y;
}

inline int Min(int x,int y){
	return x<y?x:y;
}

int find(int x){
	int tmp=x,pre;
	while(tmp!=fa[tmp])tmp=fa[tmp];
	while(x!=tmp){
		pre=fa[x];
		fa[x]=tmp;
		x=pre;
	}
	return tmp;
}

bool pan(int x){
//	printf("---------%d----------\n",x);
	in[x]=true;
	num[1]=x;
	fa[x]=x+1;
	int cnts=1,rcnts=1;
	for(int step=1;step<=t;step++){
		for(int i=1;i<=cnts;i++){
			int ks=num[i];
			int j=find(Max(1,ks-k));
			for(;j<=n;j=find(j))if(j!=ks&&!in[j]&&j!=x){
				if(j==0)return false;
				fa[j]=j+1;
				tot++;
//				printf("(%d,%d)\n",ks,j);
				in[j]=true;
				num[++rcnts]=j;
				break;
			}
		}
		cnts=rcnts;
//		printf("\n");
	}
	return true;
}

int main(){
	freopen("btp.in","r",stdin);
	freopen("btp.out","w",stdout);
	scanf("%d%d",&n,&k);
	int tmp=n;
	r=n;
	while(!(tmp&1)){tmp/=2;t++;}
	while(l<=r){
		int mid=(l+r)/2;
		memset(in,0,sizeof in);
		for(int i=1;i<=n;i++)fa[i]=i;
		bool flag=pan(mid);
		if(flag){
			if(mid>ans)ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	tot++;
	printf("%d\n",ans);
	return 0;	
}