2013 长沙网络赛 B 题 Bizarre Routine

题解

http://blog.csdn.net/u010257508/article/details/11936129

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=1e4+9;int mint[maxn],maxt[maxn],ans[maxn];int n,t,a,b;void dfs(int t,int s,int sum){    if(t>=s)    {        if(t==s) ans[t]=t;        return ;    }    sum-=s-t;    int i;    for(i=t;;i++)    if(maxt[i-t]+maxt[s-i]>=sum&&mint[i-t]+mint[s-i]<=sum) break;    int l=mint[i-t],r=maxt[i-t],mid;    while(l<r)    {        mid=l+r>>1;        if(mid+maxt[s-i]<sum) l=mid+1;        else r=mid;    }    dfs(t,i-1,l);    dfs(i+1,s,sum-l);    ans[i]=i;    int ss=(t*a+s*b)/(a+b);    swap(ans[ss],ans[i]);    if(i!=ss) swap(ans[i],ans[s]);}void solve(){    dfs(1,n,t);    for(int i=1;i<n;i++)    printf("%d ",ans[i]);    cout<<ans[n]<<endl;}int main(){    for(int i=1;i<maxn;i++) maxt[i]=i*(i-1)>>1;    mint[1]=0,mint[2]=1;    for(int i=3;i<maxn;i++) mint[i]=mint[i>>1]+mint[i-1>>1]+i-1;    while(scanf("%d %d %d %d",&n,&t,&a,&b)!=EOF)    {        if(t>maxt[n]||t<mint[n]) printf("NOWAY\n");        else solve();    }    return 0;}