fork download 
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdio.h>
  4. #include <math.h>
  5. void print_pairs_u16(unsigned short *a, size_t size) {
  6.   size_t i;
  7.   putchar('[');
  8.   for (i = 0; i < size; i += 2) {
  9.     if (0 < i) printf(", ");
  10.     printf("[%u, %u]", a[i], a[i + 1]);
  11.   }
  12.   putchar(']');
  13. }
  14. void print_pairs_u32(unsigned int *a, size_t size) {
  15.   size_t i;
  16.   putchar('[');
  17.   for (i = 0; i < size; i += 2) {
  18.     if (0 < i) printf(", ");
  19.     printf("[%u, %u]", a[i], a[i + 1]);
  20.   }
  21.   putchar(']');
  22. }
  23. static inline size_t find_index_u16(unsigned short *a, size_t size, unsigned int value) {
  24.   size_t i;
  25.   for (i = 0; i < size; i++) if (a[i] == value) return i;
  26.   return size;
  27. }
  28. static inline size_t find_index_u32(unsigned int *a, size_t size, unsigned int value) {
  29.   size_t i;
  30.   for (i = 0; i < size; i++) if (a[i] == value) return i;
  31.   return size;
  32. }
  33. #define print_pairs(a, n) _Generic((a), unsigned short * : print_pairs_u16, unsigned int * : print_pairs_u32, default : print_pairs_u32)((a), (n))
  34. #define find_index(a, n, v) _Generic((a), unsigned short * : find_index_u16, unsigned int * : find_index_u32, default : find_index_u32)((a), (n), (v))
  35. #define array_cap(a) (sizeof (a) / sizeof *(a))
  36. #define array_print_as_pairs(a) print_pairs((a), array_cap(a))
  37. #define array_find_index(a, v) find_index(a, array_cap(a), v)
  38.  
  39. typedef unsigned long long type_key;
  40. typedef unsigned short type_value_elem;
  41. typedef struct value {
  42.   type_value_elem values[4];
  43. } type_value;
  44. typedef struct entry {
  45.   type_key key;
  46.   type_value value;
  47. } type_entry;
  48. typedef unsigned int type_index;
  49. typedef struct table {
  50.   type_index bin_power, entry_power, n_entries, *bins;
  51.   type_entry *entries;
  52. } type_table;
  53. static inline type_index bins_cap(type_table *table) {
  54.   return (type_index)1 << table->bin_power;
  55. }
  56. static inline type_index entries_cap(type_table *table) {
  57.   return (type_index)1 << table->entry_power;
  58. }
  59. static inline size_t bins_n_bytes(type_table *table) {
  60.   return sizeof *table->bins * bins_cap(table);
  61. }
  62. static inline size_t entries_n_bytes(type_table *table) {
  63.   return sizeof *table->entries * entries_cap(table);
  64. }
  65. void table_inspect_bins(type_table *table) {
  66.   for (size_t i = 0; i < bins_cap(table); i++)
  67.     printf("bins[%zu]: %u\n", i, table->bins[i]);
  68. }
  69. void table_inspect(type_table *table) {
  70.   printf("table: %p\n", table);
  71.   printf("bin_power: %u\n", table->bin_power);
  72.   printf("entry_power: %u\n", table->entry_power);
  73.   printf("n_entries: %u\n", table->n_entries);
  74.   printf("bins: %p\n", table->bins);
  75.   printf("entries: %p\n", table->entries);
  76.   printf("bins_cap: %x %d\n", bins_cap(table), bins_cap(table));
  77.   printf("entries_cap: %x %d\n", entries_cap(table), entries_cap(table));
  78. }
  79. type_table *table_new(type_index bin_power, type_index entry_power) {
  80.   type_table *table = malloc(sizeof (type_table));
  81.   table->bin_power = bin_power;
  82.   table->entry_power = entry_power;
  83.   table->n_entries = 0;
  84.   table->bins = malloc(bins_n_bytes(table));
  85.   table->entries = malloc(entries_n_bytes(table));
  86.   memset(table->bins, 0, bins_n_bytes(table));
  87.   if (!table || !table->bins || !table->entries)
  88.     fprintf(stderr, "table_new: out of memory\n"), exit(EXIT_FAILURE);
  89.   return table;
  90. }
  91. void table_free(type_table *table) {
  92.   free(table->bins), free(table->entries), free(table);
  93. }
  94. static inline type_index calc_bin_index(type_table *table, type_key key) {
  95.   return (bins_cap(table) - 1) & key;
  96. }
  97. static inline type_index find_bin_index(type_table *table, type_key key) {
  98.   type_index found = calc_bin_index(table, key);
  99.   type_index collision = 0;
  100.   type_index borderline = bins_cap(table) - 1;
  101.   type_index *bins = table->bins;
  102.   type_entry *entries = table->entries;
  103.   while (bins[found] && entries[bins[found]].key != key) {
  104.     collision++;
  105.     if (borderline < collision)
  106.       fprintf(stderr, "borderline: %u, collision: %u\n", borderline, collision), exit(EXIT_FAILURE);
  107.     else
  108.       found = calc_bin_index(table, found + 1);
  109.   }
  110.   return found;
  111. }
  112. static inline void table_put_at(type_table *table, type_key key, type_value value, type_index bin_index) {
  113.   type_index borderline = entries_cap(table) - 1;
  114.   type_index *bins = table->bins;
  115.   type_entry *entries = table->entries;
  116.   if (!bins[bin_index]) {
  117.     // bins[x] == 0はビンが未使用という表現。そのため entries[0] は欠番。最初のデータは entries[1] に入る。
  118.     if (borderline < table->n_entries + 1)
  119.       fprintf(stderr, "borderline: %u, (table->n_entries + 1): %u\n", borderline, table->n_entries + 1), exit(EXIT_FAILURE);
  120.     table->n_entries++;
  121.     bins[bin_index] = table->n_entries;
  122.     entries[bins[bin_index]] = (type_entry){key, value};
  123.   } else {
  124.     // 既存のエントリに上書き。
  125.     entries[bins[bin_index]] = (type_entry){key, value};
  126.   }
  127. }
  128. void table_put(type_table *table, type_key key, type_value value) {
  129.   return table_put_at(table, key, value, find_bin_index(table, key));
  130. }
  131. static inline type_value *table_get_at(type_table *table, type_index bin_index) {
  132.   type_index *bins = table->bins;
  133.   type_entry *entries = table->entries;
  134.   return !bins[bin_index] ? 0 : &entries[bins[bin_index]].value;
  135. }
  136. type_value *table_get(type_table *table, type_key key) {
  137.   return table_get_at(table, find_bin_index(table, key));
  138. }
  139. int table_contains_key(type_table *table, type_key key) {
  140.   return !!table_get(table, key);
  141. }
  142. type_index table_size(type_table *table) {
  143.   return table->n_entries;
  144. }
  145.  
  146. static inline type_value *value_append(type_value *value, type_value_elem e) {
  147.   type_index cap = array_cap(value->values), i = array_find_index(value->values, 0);
  148.   if (i < cap)
  149.     value->values[i] = e;
  150.   else
  151.     fprintf(stderr, "value->values cap: %u, required: %u\n", cap, cap + 1), exit(EXIT_FAILURE);
  152.   return value;
  153. }
  154. struct answer {
  155.   type_key c;
  156.   type_value_elem pairs[10];
  157. };
  158. struct answer answer_from(type_value *value, type_value_elem last_b, type_key c) {
  159.   struct answer ans = {c};
  160.   size_t i, cap = array_cap(value->values);
  161.   type_value_elem a, b;
  162.   for (i = 0; i <= cap; i++) {
  163.     b = i < cap ? value->values[i] : last_b;
  164.     a = round(cbrt(c + (type_key)b * b * b));
  165.     ans.pairs[i * 2 + 0] = a;
  166.     ans.pairs[i * 2 + 1] = b;
  167.   }
  168.   return ans;
  169. }
  170. struct answer f(unsigned m) {
  171.   type_table *table = table_new(27, 24);
  172.   type_value *value = 0;
  173.   type_index index;
  174.   type_value_elem a, b;
  175.   type_key c;
  176.   struct answer ans;
  177.   for (a = 1; ; a++) {
  178.     for (b = 1; b < a; b++) {
  179.       c = (type_key)a * a * a - (type_key)b * b * b;
  180.       index = find_bin_index(table, c);
  181.       value = table_get_at(table, index);
  182.       if (!value) 
  183.         table_put_at(table, c, (type_value){b}, index);
  184.       else if (array_find_index(value->values, 0) + 1 == m) 
  185.         goto finally;
  186.       else 
  187.         value_append(value, b);
  188.     }
  189.   }
  190.  finally:
  191.   ans = answer_from(value, b, c);
  192.   table_free(table);
  193.   return ans;
  194. }
  195. int main() {
  196.   struct answer ans = f(5);
  197.   array_print_as_pairs(ans.pairs);
  198.   return 0;
  199. }
  200.  
Success #stdin #stdout 0.38s 703320KB
comments (?)
stdin 
Standard input is empty
stdout 
[[1134, 357], [1155, 504], [1246, 805], [2115, 2004], [4746, 4725]]
https://ideone.com/JnJpJW
language:
C (clang 8.0)
created:
78 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!