fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. void print_ary(int *a, size_t sz)
  5. {
  6.   int i;
  7.   for(i = 0; i < sz; ++i) printf("%d ", a[i]);
  8. }
  9.  
  10. void q_sort(int *a, int left, int right)
  11. {
  12.   int i = left, j = right, key = a[(left + right) / 2];
  13.   if(left >= right) return;
  14.   // printf("i(%d,%d) ", left, right); print_ary(a, 5); printf("\n");
  15.   while(1){
  16.     for( ; i <= j; ++i) if(a[i] >= key) break;
  17.     for( ; j >= i; --j) if(a[j] <= key) break;
  18.     if(i >= j) break;
  19.     else{ int t = a[j]; a[j] = a[i]; a[i] = t; ++i; --j; }
  20.   }
  21.   if(right <= left + 1) return;
  22.   if(i > left) q_sort(a, left, i);
  23.   if(right > j) q_sort(a, j, right);
  24.   // printf("o(%d,%d) ", left, right); print_ary(a, 5); printf("\n");
  25. }
  26.  
  27. int fact(int n)
  28. {
  29.   if(n <= 1) return 1;
  30.   return n * fact(n - 1);
  31. }
  32.  
  33. int ipow(int x, int y)
  34. {
  35.   int n, r = x;
  36.   if(!y) return 1;
  37.   for(n = 1; n < y; ++n) r *= x;
  38.   return r;
  39. }
  40.  
  41. void perm(int *a, int sz, int m)
  42. {
  43.   int n, p;
  44.   int *b = (int *)malloc((sz - 1) * sizeof(int));
  45.   if(!b) return;
  46.   for(n = 0; n < (sz - 1); ++n){
  47.     int o = n + 2;
  48.     b[n] = (n ? p : m) % o;
  49.     p = (n ? p : m) / o;
  50.   }
  51.   for(n = 0; n < sz; ++n) a[n] = sz - n;
  52.   for(n = 0; n < (sz - 1); ++n){
  53.     int q = b[sz - 2 - n];
  54.     int r = a[n + q];
  55.     for( ; q > 0; --q) a[n + q] = a[n + q - 1];
  56.     a[n] = r;
  57.   }
  58.   free(b);
  59. }
  60.  
  61. void combi(int *a, int sz, int m)
  62. {
  63.   int n;
  64.   for(n = 0; n < sz; ++n){
  65.     volatile int o = m / ipow(sz, n);
  66.     a[n] = o % sz + 1;
  67.   }
  68. }
  69.  
  70. int main(int ac, char **av)
  71. {
  72.   int ary[6];
  73.   int l, m, n, o = 0;
  74.   for(l = 5; l <= 6; ++l){
  75. #if(0) // OK
  76.     for(m = 0; m < fact(l); ++m){
  77.       perm(ary, l, m);
  78. #else // BAD
  79.     for(m = 0; m < ipow(l, l); ++m){
  80.       combi(ary, l, m);
  81. #endif
  82.       print_ary(ary, l); printf(" -> ");
  83.       q_sort(ary, 0, l - 1);
  84.       print_ary(ary, l); printf(" -> ");
  85.       for(n = 1; n < l; ++n) if(ary[n] < ary[n - 1]){ n = 0; ++o; break; }
  86.       printf("%s\n", n ? "OK" : "BAD");
  87.     }
  88.   }
  89.   if(o) printf("\a%d error(s) found\n", o);
  90.   else printf("All Correct\n");
  91.   return 0;
  92. }
Time limit exceeded #stdin #stdout 5s 2292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SOCKxw
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

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!