結果
問題 | No.8011 品物の並び替え (Extra) |
ユーザー | ciel |
提出日時 | 2015-05-02 21:02:26 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 25,554 bytes |
コンパイル時間 | 534 ms |
コンパイル使用メモリ | 37,760 KB |
実行使用メモリ | 128,724 KB |
最終ジャッジ日時 | 2024-07-05 17:34:39 |
合計ジャッジ時間 | 9,360 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | AC | 1,045 ms
128,724 KB |
testcase_04 | AC | 614 ms
65,052 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 562 ms
65,048 KB |
testcase_08 | WA | - |
コンパイルメッセージ
main.cpp: In function ‘tournament* read_tournament(FILE*)’: main.cpp:266:10: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 266 | fail("No data for read_tournament"); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:271:19: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 271 | if(n != 2) fail("Wrong number of entries in header row)"); // | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:278:10: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 278 | fail("I didn't understand the starting line"); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:280:10: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 280 | fail("Empty tournament"); | ^~~~~~~~~~~~~~~~~~ main.cpp:288:28: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 288 | if(rest == check) fail("failed to parse line"); | ^~~~~~~~~~~~~~~~~~~~~~ main.cpp:291:28: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 291 | if(rest == check) fail("failed to parse line"); | ^~~~~~~~~~~~~~~~~~~~~~ main.cpp:294:28: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 294 | if(rest == check) fail("failed to parse line"); | ^~~~~~~~~~~~~~~~~~~~~~ main.cpp:296:31: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings] 296 | if(i >= n || j >= n) fail("index out of bounds"); | ^~~~~~~~~~~~~~~~~~~~~
ソースコード
//Submitting this code should not be good if I weren't the author... //C99 or C++98. #include <stdlib.h> #include <stdio.h> #include <stdint.h> #include <string.h> #include <ctype.h> #include <assert.h> #include <time.h> #include <unistd.h> //fas_tournament.h typedef struct { size_t size; double entries[]; } tournament; void enable_fas_tournament_debug(int x); tournament *new_tournament(size_t n); void del_tournament(tournament *t); double tournament_get(tournament *t, size_t i, size_t j); void tournament_set(tournament *t, size_t i, size_t j, double x); tournament *read_tournament(FILE *f); tournament *normalize_tournament(tournament *t); double best_score_lower_bound(tournament *t, size_t n, size_t *items); double score_fas_tournament(tournament *t, size_t count, size_t *data); size_t *optimal_ordering(tournament *t, size_t *results); size_t tie_starting_from(tournament *t, size_t n, size_t *items, size_t start_index); size_t condorcet_boundary_from(tournament *t, size_t n, size_t *items, size_t start_index); //optimisation_table.h typedef struct{ uint64_t hash; size_t length; size_t *data; double value; } ot_entry; typedef struct { size_t length; size_t occupancy; ot_entry *entries; } optimisation_table; optimisation_table *optimisation_table_new(); void optimisation_table_del(optimisation_table *ot); ot_entry *optimisation_table_lookup(optimisation_table *ot, size_t length, size_t *data); //permutations.h size_t next_permutation(size_t length, size_t *data); void shuffle(size_t length, size_t *data); void reverse(size_t *s, size_t *e); size_t random_number(size_t n); void generate_shuffled_range(size_t length, size_t *data); //population.h typedef struct { double score; size_t *data; } population_member; typedef struct { size_t members_size; size_t population_count; population_member members[1]; } population; population *population_new(size_t population_count, size_t members_size); void population_del(population *p); void population_heapify(population *p); int population_contains(population *p, double key, size_t *data); population_member fittest_member(population *p); void population_push(population *p, double key, size_t *data); //fas_tournament.c #define ACCURACY 0.001 #define SMOOTHING 0.05 #define MAX_MISSES 5 #define MIN_IMPROVEMENT 0.00001 #define FASDEBUG(...) if(_enable_fas_tournament_debug) fprintf(stderr, __VA_ARGS__); int _enable_fas_tournament_debug = 0; void enable_fas_tournament_debug(int x){ _enable_fas_tournament_debug = x; } tournament *new_tournament(size_t n){ size_t size = sizeof(tournament) + sizeof(double) * n * n; tournament *t = (tournament *)malloc(size); memset(t, '\0', size); t->size = n; return t; } tournament *normalize_tournament(tournament *t){ double max_total = 0.0; for(size_t i = 0; i < t->size; i++){ for(size_t j = i + 1; j < t->size; j++){ double total = tournament_get(t, i, j) + tournament_get(t, j, i); if(total > max_total) { max_total = total; } } } tournament *nt = new_tournament(t->size); if(max_total <= 0.0){ for(size_t i = 0; i < t->size; i++){ for(size_t j = 0; j < t->size; j++){ tournament_set(nt, i, j, 0.5); } } } else { for(size_t i = 0; i < t->size; i++){ tournament_set(nt, i, i, 0.5); for(size_t j = i + 1; j < t->size; j++){ double tij = tournament_get(t, i, j); double tji = tournament_get(t, j, i); double bonus = (max_total - (tij + tji)) / 2; tij += bonus; tji += bonus; tij /= max_total; tji /= max_total; tournament_set(nt, i, j, tij); tournament_set(nt, j, i, tji); } } } return nt; } void del_tournament(tournament *t){ free(t); } typedef struct { size_t *buffer; optimisation_table *opt_table; tournament *_tournament; } fas_optimiser; fas_optimiser *new_optimiser(tournament *t){ fas_optimiser *it = (fas_optimiser *)malloc(sizeof(fas_optimiser)); it->buffer = (size_t *)malloc(sizeof(size_t) * t->size); it->opt_table = optimisation_table_new(); it->_tournament = t; return it; } void del_optimiser(fas_optimiser *o){ free(o->buffer); optimisation_table_del(o->opt_table); free(o); } void reset_optimiser(fas_optimiser *opt){ optimisation_table_del(opt->opt_table); opt->opt_table = optimisation_table_new(); } size_t tournament_size(tournament *t){ return t->size; } inline double tournament_get(tournament *t, size_t i, size_t j){ size_t n = t->size; assert(i < n); assert(j < n); return t->entries[n * i + j]; } inline void tournament_set(tournament *t, size_t i, size_t j, double x){ size_t n = t->size; assert(i < n); assert(j < n); t->entries[n * i + j] = x; } double score_fas_tournament(tournament *t, size_t count, size_t *data){ double score = 0.0; for(size_t i = 0; i < count; i++){ for(size_t j = i + 1; j < count; j++){ score += t->entries[data[i] * t->size + data[j]]; } } return score; } static size_t count_tokens(char *c){ if(*c == '\0') return 0; size_t count = 0; int in_token = !isspace(*c); while(*c){ if(isspace(*c)){ if(in_token) count++; in_token = 0; } else { in_token = 1; } c++; } if(in_token) count++; return count; } static int read_line(size_t *buffer_size, char **buffer, FILE *f){ if(!*buffer) *buffer = (char *)malloc(*buffer_size); size_t written = 0; for(;;){ char c = getc(f); if(c == EOF){ if(written) break; else return 0; } if(c == '\n') break; if(written == *buffer_size){ *buffer_size *= 2; *buffer = (char *)realloc(*buffer, *buffer_size); } (*buffer)[written++] = c; } if(written == *buffer_size){ *buffer_size *= 2; *buffer = (char *)realloc(*buffer, *buffer_size); } (*buffer)[written] = '\0'; return 1; } static void fail(char *msg){ fprintf(stderr, "%s\n", msg); exit(1); } tournament *read_tournament(FILE *f){ size_t length = 1024; char *line = NULL; tournament *t; if(!read_line(&length, &line, f)){ fail("No data for read_tournament"); } size_t n = count_tokens(line); if(n != 2) fail("Wrong number of entries in header row)"); // char *rest = line; n = strtoul(line, &rest, 0); if(line == rest){ fail("I didn't understand the starting line"); } else if (n <= 0){ fail("Empty tournament"); } t = new_tournament(n); while(read_line(&length, &line, f)){ char *check = line; size_t i = strtoul(line, &rest, 0); if(rest == check) fail("failed to parse line"); check = rest; size_t j = strtoul(rest, &rest, 0); if(rest == check) fail("failed to parse line"); check = rest; double f = strtod(rest, &rest); if(rest == check) fail("failed to parse line"); if(i >= n || j >= n) fail("index out of bounds"); t->entries[n * i + j] += f; } free(line); fclose(f); return t; } static int tournament_compare(tournament *t, size_t i, size_t j){ double x = tournament_get(t, i, j); double y = tournament_get(t, j, i); if(x < y + ACCURACY && x > y - ACCURACY) return 0; if(x >= y) return -1; if(y >= x) return +1; return 0; } static inline void swap(size_t *x, size_t *y){ if(x == y) return; size_t z = *x; *x = *y; *y = z; } int table_optimise(fas_optimiser *o, size_t n, size_t *items){ tournament *t = o->_tournament; if(n <= 1) return 0; if(n == 2){ int c = tournament_compare(t, items[0], items[1]); if(c > 0) swap(items, items+1); return c > 0; } ot_entry *ote = optimisation_table_lookup(o->opt_table, n, items); double existing_score = score_fas_tournament(t, n, items); if(ote->value >= 0){ // We already have a best calculation for this entry if(existing_score < ote->value){ // We know a better way to order these memcpy(items, ote->data, n * sizeof(size_t)); return 1; } else { return 0; } } else { size_t *best_value_seen = (size_t *)malloc(n * sizeof(size_t)); size_t *pristine_copy = (size_t *)malloc(n * sizeof(size_t)); memcpy(pristine_copy, items, n * sizeof(size_t)); memcpy(best_value_seen, items, n * sizeof(size_t)); int changed = 0; double best_score_so_far = existing_score; for(size_t i = 0; i < n; i++){ memcpy(items, pristine_copy, n * sizeof(size_t)); swap(items, items + i); table_optimise(o, n-1, items+1); double new_score = score_fas_tournament(t, n, items); if(new_score > best_score_so_far){ memcpy(best_value_seen, items, n * sizeof(size_t)); changed = 1; best_score_so_far = new_score; } } ote = optimisation_table_lookup(o->opt_table, n, items); memcpy(items, best_value_seen, n * sizeof(size_t)); ote->value = best_score_so_far; memcpy(ote->data, items, n * sizeof(size_t)); free(best_value_seen); free(pristine_copy); return changed; } } int window_optimise(fas_optimiser *o, size_t n, size_t *items, size_t window){ if(n <= window){ return table_optimise(o, n, items); } double last_score = score_fas_tournament(o->_tournament, n, items); int changed_at_all = 0; int changed = 1; while(changed){ changed = 0; for(size_t i = 0; i < n - window; i++){ changed |= table_optimise(o, window, items + i); } double new_score = score_fas_tournament(o->_tournament, n, items); double improvement = (new_score - last_score) / last_score; changed_at_all |= changed; if(improvement < MIN_IMPROVEMENT) break; last_score = new_score; } return changed_at_all; } typedef struct { size_t index; double score; } index_with_score; int compare_index_with_score(const void *xx, const void *yy){ index_with_score *x = (index_with_score*)xx; index_with_score *y = (index_with_score*)yy; if(x->score < y->score) return -1; if(x->score > y->score) return 1; return 0; } // Insertion sort for now. Everything else is O(n^2) anyway static void move_pointer_right(size_t *x, size_t offset){ while(offset){ size_t *next = x + 1; swap(x, next); x = next; offset--; } } static void move_pointer_left(size_t *x, size_t offset){ while(offset){ size_t *next = x - 1; swap(x, next); x = next; offset--; } } int single_move_optimise(fas_optimiser *o, size_t n, size_t *items){ tournament *t = o->_tournament; int changed = 1; int changed_at_all = 0; while(changed){ changed = 0; for(size_t index_of_interest = 0; index_of_interest < n; index_of_interest++){ double score_delta = 0; if(index_of_interest > 0){ size_t j = index_of_interest; do { j--; score_delta += tournament_get(t, items[index_of_interest], items[j]); score_delta -= tournament_get(t, items[j], items[index_of_interest]); if(score_delta > 0){ move_pointer_left(items+index_of_interest, index_of_interest - j); changed = 1; break; } } while(j > 0); } for(size_t j = index_of_interest + 1; j < n; j++){ score_delta += tournament_get(t, items[j], items[index_of_interest]); score_delta -= tournament_get(t, items[index_of_interest], items[j]); if(score_delta > 0){ move_pointer_right(items+index_of_interest, j - index_of_interest); changed = 1; changed_at_all = 1; break; } } } } return changed_at_all; } size_t *integer_range(size_t n){ size_t *results = (size_t *)malloc(sizeof(size_t) * n); for(size_t i = 0; i < n; i++){ results[i] = i; } return results; } int force_connectivity(fas_optimiser *o, size_t n, size_t *items){ if(!n) return 0; int changed = 0; tournament *t = o->_tournament; for(size_t i = 0; i < n - 1; i++){ size_t j = i + 1; while(j < n && !tournament_compare(t, items[i], items[j])) j++; if(j < n){ changed = 1; move_pointer_left(items + j, (j - i - 1)); } } return changed; } int local_sort(fas_optimiser *o, size_t n, size_t *items){ tournament *t = o->_tournament; int changed = 0; for(size_t i = 1; i < n; i++){ size_t j = i; while(j > 0 && tournament_compare(t, items[j], items[j - 1]) <= 0){ changed = 1; swap(items + j, items + j - 1); j--; } } return changed; } int stride_optimise(fas_optimiser *o, size_t n, size_t *data, size_t stride){ int changed = 0; while(n > stride){ changed |= table_optimise(o, stride, data); data += stride; n -= stride; } changed |= table_optimise(o, n, data); return changed; } int kwik_sort(fas_optimiser *o, size_t n, size_t *data, size_t depth){ if(n <= 1) return 0; if(depth >= 10) return 0; size_t *lt = (size_t *)malloc(n * sizeof(size_t)); size_t *gt = (size_t *)malloc(n * sizeof(size_t)); size_t ltn = 0; size_t gtn = 0; size_t pivot = data[random_number(n)]; for(size_t i = 0; i < n; i++){ int c = tournament_compare(o->_tournament, data[i], pivot); if(c < 0) lt[ltn++] = data[i]; else if(c == 0){ if(random_number(2)){ lt[ltn++] = data[i]; } else { gt[gtn++] = data[i]; } } else gt[gtn++] = data[i]; } depth++; kwik_sort(o, ltn, lt, depth); kwik_sort(o, gtn, gt, depth); memcpy(data, lt, sizeof(size_t) * ltn); memcpy(data + ltn, gt, sizeof(size_t) * gtn); free(lt); free(gt); return 1; } size_t *copy_items(size_t n, size_t *items){ size_t *copy = (size_t *)calloc(n, sizeof(size_t)); memcpy(copy, items, n * sizeof(size_t)); return copy; } population *build_population(fas_optimiser *o, size_t n, size_t *items, size_t ps){ population *p = population_new(ps, n); for(size_t i = 0; i < ps; i++){ size_t *data = copy_items(n, items); kwik_sort(o, n, data, 0), p->members[i].data = data; p->members[i].score = score_fas_tournament(o->_tournament, n, data); } population_heapify(p); return p; } int coin_flip(){ return random_number(2); } void mutate(fas_optimiser *o, size_t n, size_t *data){ size_t i = random_number(n); size_t j; do{ j = random_number(n); } while(i == j); if(j < i){ size_t k = i; i = j; j = k; } switch(random_number(5)){ case 0: reverse(data + i, data + j); break; case 1: swap(data + i, data + j); break; case 2: if(coin_flip()){ move_pointer_right(data + i, j - i); } else { move_pointer_left(data + j, j - i); } break; case 3: if(j > i + 12) j = i + 12; table_optimise(o, j - i, data + i); break; case 4: local_sort(o, j - i, data + i); break; } } void improve_population(fas_optimiser *o, population *p, size_t count){ tournament *t = o->_tournament; size_t n = t->size; size_t *data = (size_t *)malloc(n * sizeof(size_t)); for(size_t i = 0; i < count; i++){ size_t *candidate = p->members[random_number(p->population_count)].data; memcpy(data, candidate, n * sizeof(size_t)); mutate(o, n, data); double score = score_fas_tournament(t, t->size, candidate); if(!population_contains(p, score, data)){ population_push(p, score, data); } } free(data); } void population_optimise(fas_optimiser *o, size_t n, size_t *items, size_t initial_size, size_t generations){ population *p = build_population(o, n, items, initial_size); improve_population(o, p, generations); memcpy(items, fittest_member(p).data, n * sizeof(size_t)); population_del(p); } void comprehensive_smoothing(fas_optimiser *o, size_t n, size_t *results){ stride_optimise(o, n, results, 11); local_sort(o, n, results); stride_optimise(o, n, results, 13); local_sort(o, n, results); reset_optimiser(o); for(int i = 0; i < 10; i++){ int changed = 0; changed |= stride_optimise(o, n, results, 12); changed |= stride_optimise(o, n, results, 7); changed |= local_sort(o, n, results); reset_optimiser(o); if(!changed) break; single_move_optimise(o,n,results); } } size_t *optimal_ordering(tournament *t, size_t *results){ fas_optimiser *o = new_optimiser(t); size_t n = t->size; if(results == NULL){ results = integer_range(n); } if(n <= 15){ table_optimise(o, n, results); del_optimiser(o); return results; } population_optimise(o, n, results, 500, 1000); comprehensive_smoothing(o, n, results); window_optimise(o, n, results, 10); local_sort(o, n, results); del_optimiser(o); return results; } size_t tie_starting_from(tournament *t, size_t n, size_t *items, size_t start_index){ for(size_t i = start_index+1; i < n; i++){ for(size_t j = start_index; j < i; j++){ int c = tournament_compare(t, items[i], items[j]); if(c) return i; } } return n; } size_t condorcet_boundary_from(tournament *t, size_t n, size_t *items, size_t start_index){ size_t boundary = start_index; int boundary_change = 0; do { boundary_change = 0; for(size_t i = start_index; i <= boundary; i++){ for(size_t j = boundary + 1; j < n; j++){ if(tournament_compare(t, items[j], items[i]) <= 0){ boundary = j; boundary_change = 1; break; } } } } while(boundary_change); return boundary; } //optimisation_table.c #define MAX_OCCUPANCY_RATIO 0.9 #define DEFAULT_TABLE_SIZE 65536 inline int set_contains_value(size_t length, size_t *xs, size_t x){ for(size_t i = 0; i < length; i++) if(xs[i] == x) return 1; return 0; } int set_compare(size_t length, size_t *x, size_t *y){ for(size_t i = 0; i < length; i++) if(!set_contains_value(length, y, x[i])) return 0; return 1; } uint64_t hash64(uint64_t key) { key = (~key) + (key << 21); key = key ^ (key >> 24); key = (key + (key << 3)) + (key << 8); key = key ^ (key >> 14); key = (key + (key << 2)) + (key << 4); key = key ^ (key >> 28); key = key + (key << 31); return key; } uint64_t set_hash(size_t length, size_t *x){ uint64_t result = 0; for(size_t i = 0; i < length; i++) result ^= hash64(x[i]); return result; } size_t *clone_set(size_t length, size_t *x){ size_t *result = (size_t *)malloc(length * sizeof(size_t)); memcpy(result, x, length * sizeof(size_t)); return result; } optimisation_table *optimisation_table_new(){ optimisation_table *result = (optimisation_table *)malloc(sizeof(optimisation_table)); result->occupancy = 0; result->length=DEFAULT_TABLE_SIZE; result->entries = (ot_entry *)calloc(DEFAULT_TABLE_SIZE, sizeof(ot_entry)); return result; } void optimisation_table_del(optimisation_table *ot){ for(size_t i = 0; i < ot->length; i++) free(ot->entries[i].data); free(ot->entries); free(ot); } ot_entry *optimisation_table_lookup_internal(optimisation_table *ot, size_t length, size_t *data, int must_copy){ uint64_t h = set_hash(length, data); size_t mask = ot->length - 1; size_t p = (size_t)(h & mask); while(1){ ot_entry *ce = ot->entries + p; if(!ce->length){ if(ot->occupancy > ot->length * MAX_OCCUPANCY_RATIO){ size_t old_length = ot->length; ot_entry *old_entries = ot->entries; ot->length *= 2; ot->entries = (ot_entry *)calloc(ot->length, sizeof(ot_entry)); for(size_t i = 0; i < old_length; i++){ if(old_entries[i].length){ optimisation_table_lookup_internal(ot, old_entries[i].length, old_entries[i].data, 0)->value = old_entries[i].value; } } free(old_entries); return optimisation_table_lookup_internal(ot, length, data, must_copy); } else { ce->length = length; ce->hash = h; ce->data = (must_copy ? clone_set(length, data) : data); ce->value = -1; ot->occupancy++; return ce; } } else { if((ce->length == length) && (ce->hash == h) && set_compare(length, data, ce->data)) return ce; } p = (p + 1) & mask; } } ot_entry *optimisation_table_lookup(optimisation_table *ot, size_t length, size_t *data){ return optimisation_table_lookup_internal(ot, length, data, 1); } //permutations.c // Permutations of arrays of size_t void reverse(size_t *s, size_t *e){ while(s < e){ swap(s, e); s++; e--; } } // Returns index of first index altered or length if no changes size_t next_permutation(size_t length, size_t *data){ if(length <= 1) return length; // Guaranteed not to overflow by above size_t k = length - 2; while(data[k] >= data[k+1]){ if(k > 0) k--; // We are in decreasing order and thus are done. else return length; } // Now we have data[k] < data[k+1] // We want to find the largest index l such that data[k] < data[l] size_t l = k + 1; for(size_t s = l; s < length; s++){ if(data[k] < data[s]) l = s; } swap(data + k, data + l); reverse(data + k + 1, data + length - 1); return k; } inline static size_t saturate(size_t v){ v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v |= v >> 32; return v; } size_t random_number(size_t n){ size_t mask = saturate(n); size_t result; for(;;){ result = rand() & mask; if(result < n) return result; } } void shuffle(size_t length, size_t *data){ for(size_t k = length - 1; k > 0; k--){ size_t j = random_number(k+1); assert(j <= k); swap(data + j, data + k); } } void generate_shuffled_range(size_t length, size_t *data){ data[0] = 0; for(size_t i = 1; i < length; i++){ size_t j = random_number(i + 1); if(j < i) data[i] = data[j]; data[j] = i; } } //population.c population *population_new(size_t population_count, size_t members_size){ size_t size = sizeof(population_member) * population_count + sizeof(population); population *p = (population *)malloc(size); memset(p, '\0', size); p->members_size = members_size; p->population_count = population_count; return p; } void population_del(population *p){ for(size_t i = 0; i < p->population_count; i++) free(p->members[i].data); free(p); } static void population_swap(population_member *ms, size_t i, size_t j){ population_member x = ms[i]; ms[i] = ms[j]; ms[j] = x; } static void bubble_down(population *p, size_t i){ if(i >= p->population_count) return; size_t c1 = 2 * i + 1; size_t c2 = 2 * i + 2; if(c1 >= p->population_count) return; population_member *cs = p->members; size_t smallest_child = (c2 >= p->population_count) ? c1 : (cs[c1].score <= cs[c2].score ? c1 : c2); if(cs[smallest_child].score < cs[i].score){ population_swap(cs, i, smallest_child); bubble_down(p, smallest_child); } } static void heapify_from(population *p, size_t i){ if(i >= p->population_count) return; heapify_from(p, 2 * i + 1); heapify_from(p, 2 * i + 2); bubble_down(p, i); } void population_heapify(population *p){ heapify_from(p, 0); } int population_contains_under(population *p, double key, size_t *data, size_t i){ if(i >= p->population_count) return 0; if(key < p->members[i].score) return 0; if(memcmp(data, p->members[i].data, p->members_size * sizeof(size_t))) return 1; return population_contains_under(p, key, data, 2*i + 1) || population_contains_under(p, key, data, 2*i + 2); } int population_contains(population *p, double key, size_t *data){ return population_contains_under(p, key, data, 0); } population_member fittest_member(population *p){ population_member *best_member = p->members; for(size_t i = 1; i < p->population_count; i++){ if(p->members[i].score > best_member->score){ best_member = p->members + i; } } return *best_member; } void population_push(population *p, double key, size_t *data){ p->members[0].score = key; memcpy(p->members[0].data, data, p->members_size* sizeof(size_t)); bubble_down(p, 0); } //fas.c int main(int argc, char **argv){ srand(time(NULL) ^ getpid()); enable_fas_tournament_debug(getenv("DEBUG") != NULL); FILE *argf = NULL; if(argc > 1){ if(argc > 2){ fprintf(stderr, "Usage: fas [inputfile]\n"); exit(1); } argf = fopen(argv[1], "r"); if(!argf){ fprintf(stderr, "Unable to open file %s for reading\n", argv[1]); exit(1); } } else { argf = stdin; } tournament *t = read_tournament(argf); size_t n = t->size; size_t *items = optimal_ordering(t, NULL); printf("%.0f", score_fas_tournament(t, n, items)); //printf("Optimal ordering:"); size_t i = 0; size_t next_boundary = condorcet_boundary_from(t, n, items, i); for(;;){ size_t next_i = tie_starting_from(t, n, items, i); if(next_i > i + 1){ //printf(" ["); for(size_t j = i; j < next_i; j++){ if(j > i) printf(" "); printf("%lu", items[j]); } //printf("]"); } else { printf(" %lu", items[i]); } if(next_i == n) break; i = next_i; if(i > next_boundary){ //printf(" ||"); next_boundary = condorcet_boundary_from(t, n, items, i); } } printf("\n"); free(items); del_tournament(t); return 0; }