Poj Solution 3063

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

#include <stdio.h>
#include <stdlib.h>


int m, n;
int s0[5000], s1[5000];
int mem[2][10000], *a = mem[0], *b = mem[1];
int w0, w1, b0, b1, sum;

#define mine( a, b ) ((a)<(b)?(a):(b))

void fill( ) {
    int i;
    int m0 = 0, m1 = 0;
    w0 = w1 = b0 = b1 = 0;
    for( i=0; i<n; i++ ) {
        if( m1 == n/2 ) {
            w0 += a[i];
            s0[m0++] = i;
        }
        else if( m0 == n/2 ) {
            w1 += a[i], b1 += b[i];
            s1[m1++] = i;
        }
        else if( a[i] > b[i] ) {
            if( w0-b0<w1-b1 ) {
                w0 += a[i], b0 += b[i];
                s0[m0++] = i;
            }
            else {
                w1 += a[i], b1 += b[i];
                s1[m1++] = i;
            }
        }
        else {
            if( w0-b0>w1-b1 ) {
                w0 += a[i], b0 += b[i];
                s0[m0++] = i;
            }
            else {
                w1 += a[i], b1 += b[i];
                s1[m1++] = i;
            }
        }
    }
    sum = n/2*m;
    return;
}


double random( int count ) {
    int i, j, k;
    int nw0, nw1;
    double r, t;
    r = mine( 1.0*w0/sum, 1.0*w1/sum );
    while( count-- ) {
        i = rand()%(n/2);
        j = rand()%(n/2);
        nw0 = w0-a[s0[i]]+a[s1[j]];
        nw1 = w1-a[s1[j]]+a[s0[i]];
        
        t = mine( 1.0*nw0/sum, 1.0*nw1/sum );

        if( t > r ) {
            k = s0[i]; s0[i] = s1[j]; s1[j] = k;
            w0 = nw0, w1 = nw1;
            r = t;
        }
    }
    return r;
}


int main( ) {
    int i, *temp;
    double ans, t;
    char c;

    while( scanf( "%d", &n ) == 1 ) {

        scanf( "%d", &m );
        for( i=0; i<n; i++ )
            scanf( "%d%d", &a[i], &b[i] );
        fill( );

        ans = random( n*1000 );
        c = 'W';

        temp = a; a = b; b = temp;

        fill( );
        t = random( n*1000 );
        if( t > ans )
            ans = t, c = 'B';

        if( ans <= 0.5 )
            printf( "No solutionn" );
        else
            printf( "%c %.2lfn", c, ans*100 );
    }
    return 0;
}