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;

}