結果

問題 No.8011 品物の並び替え (Extra)
ユーザー ciel
提出日時 2015-05-02 21:12:12
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,064 ms / 5,000 ms
コード長 25,555 bytes
コンパイル時間 568 ms
コンパイル使用メモリ 37,760 KB
実行使用メモリ 65,348 KB
最終ジャッジ日時 2024-07-05 17:35:17
合計ジャッジ時間 10,037 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
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");
      |                               ^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

//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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0