Poj Solution 1148

http://poj.org/problem?id=1148

#include <stdio.h>
#include <algorithm>
using namespace std;

int num[20000], n;
int ans_x[10000], ans_y[10000],sign_x[10000], sign_y[10000];
const int xsign[]={ 1, -1, -1, 1 },ysign[]={ 1, 1, -1, -1}, h[]={ 1, -1};

void creat(int end, int num[], int sign[], int ans[], int last_sign)
{
    if( end == 0 )
    {
        ans[0] = num[0]*last_sign;
        return ;
    }

    if( last_sign == sign[end-1])
    {
        ans[end]=num[0]*last_sign*h[end%2];
        creat(end-1,num+1,sign,ans,last_sign);
    }
    else
    {
        ans[end] = num[end]*last_sign;
        creat(end-1,num,sign,ans,-last_sign);
    }
    return ;
}


int main()
{
    int i, j, t;
    scanf( "%d", &n );
    for(i=0;i<2*n;i++)
        scanf("%d",&num[i]);
    
    for(i=0;i<n;i++)
    {
        scanf("%d",&t);
        sign_x[i]=xsign[t-1];
        sign_y[i]=ysign[t-1];
    }

    std::sort(num,num+2*n);

    creat(n-1,num,sign_x,ans_x,sign_x[n-1]);
    creat(n-1,num+n,sign_y,ans_y,sign_y[n-1]);

    for(i=0;i<n;i++)
    {
        if(ans_x[i]>0)printf("+");
        printf("%d ",ans_x[i]);
        if(ans_y[i]>0)printf("+");
        printf("%dn",ans_y[i]);
    }

    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *