I realized I made an error, but it wouldn't let me edit it... so here is another giant block of code:
PHP Code:
//#CLIENTSIDE
function onWeaponFired() {
// Bad match array
temp.bad = {
{91,50},
{60,230},
{132,399},
{52,293},
{22,25},
{83,293},
{83,82}
};
// Generate students array
temp.students = new[400];
for (temp.i = 0; temp.i < 400; temp.i++)
temp.students[temp.i] = temp.i;
// START of exercise
temp.start = timevar2;
// Shuffle students array
temp.n = temp.students.size();
for (temp.i = 0; temp.i < temp.n - 1; temp.i++) {
temp.j = temp.i + random(0,32767) / (32767 / (temp.n - temp.i) + 1);
temp.t = temp.students[temp.j];
temp.students[temp.j] = temp.students[temp.i];
temp.students[temp.i] = temp.t;
}
// Heapsort the bad match array
temp.bad.sortascending();
temp.pairs = new[50];
temp.i = 0;
while (temp.i < 50) {
temp.pair = {temp.students[temp.x], temp.students[temp.x+1]};
// Binary search for the current pair in the bad pairs
if (binarysearcharray(temp.bad, temp.pair) == -1) {
// Add it
temp.pairs[temp.i] = temp.pair;
temp.students.remove(temp.students[temp.x]);
temp.students.remove(temp.students[temp.y]);
temp.i++;
temp.x = 0;
temp.y = 0;
} else {
// Look more
if (temp.y == temp.students.size()) {
temp.x++;
temp.y = 0;
} else {
temp.y++;
}
}
}
// END of exercise
temp.time = timevar2 - temp.start;
player.chat = temp.pairs;
echo (temp.time);
}
// Modified binary search
function binarysearcharray(temp.a, temp.v) {
temp.low = 0;
temp.high = temp.a.size()-1;
while (temp.low <= temp.high) {
temp.mid = (temp.low + temp.high) /2;
if (temp.a[temp.mid][0] > temp.v[0] || temp.a[temp.mid][0] == temp.v[0] && temp.a[temp.mid][1] > temp.v[1])
temp.high = temp.mid - 1;
else if (temp.a[temp.mid][0] < temp.v[0] || temp.a[temp.mid][0] == temp.v[0] && temp.a[temp.mid][1] < temp.v[1])
temp.low = temp.mid +1;
else
return temp.mid;
}
return -1;
}
Worst case is actually O(n**2 log n log m), but it uses Randomization and Restriction, so it's considerably fast than the worst case.