# 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;
}

```
This entry was posted in poj. Bookmark the permalink.