Poj Solution 2454

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

#include"stdio.h"
#include"memory.h"
#include"algorithm"
#include"stdlib.h"

using namespace std;

typedef pair<int,int> city;

city c[180];
int n, k;


void init()
{
    int i;
    scanf( "%d", &n );
    k = n;
    n *= 3;

    for( i=0; i<n; i++ )
    {
        scanf( "%d", &c[i].first );
        c[i].second = i;
    }

    sort( c, c+n );
    
}

int a[60],b[60];


void search( int s1, int s2, int a[60], int b[60] , int s )
{
    int x, y, i, j;
    while( s1 <= s || s2 <= s )
    {
        i = rand()%k;
        j = rand()%k;
        x = c[a[i]].first;
        y = c[b[j]].first;

        s1 += y - x;
        s2 += x - y;
        swap( a[i], b[j] );
    }
}
    


void doit()
{
    int i,j,t,h,s1=0,s2=0;
    
    for( i=k; i<n; i++ )
    if( ( i - k ) % 2 == 0 )
    {
        s1 += c[i].first;
        a[ ( i - k ) / 2 ] = i;
    }
    else
    {
        s2 += c[i].first;
        b[ ( i - k ) / 2 ] = i;
    }

    if( s1 <= k*500 )
    search( s1, s2, a, b, k*500 );
    
    for( i=0; i<k; i++ )
    printf( "%dn", c[a[i]].second+1 );
    
    for( i=0; i<k; i++ )
    printf( "%dn", c[b[i]].second+1 );
    
    for( i=0; i<k; i++ )
    printf( "%dn", c[i].second+1 );

}

int main()
{
    init();
    doit();

    return 0;
}