結果

問題 No.14 最小公倍数ソート
ユーザー mudbdbmudbdb
提出日時 2015-06-25 22:33:24
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 4,377 ms / 5,000 ms
コード長 1,289 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 26,448 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-22 00:43:31
合計ジャッジ時間 49,644 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 45 ms
4,380 KB
testcase_04 AC 4,377 ms
4,376 KB
testcase_05 AC 1,459 ms
4,380 KB
testcase_06 AC 1,711 ms
4,380 KB
testcase_07 AC 2,238 ms
4,380 KB
testcase_08 AC 2,951 ms
4,376 KB
testcase_09 AC 3,992 ms
4,380 KB
testcase_10 AC 3,935 ms
4,380 KB
testcase_11 AC 4,079 ms
4,380 KB
testcase_12 AC 4,191 ms
4,380 KB
testcase_13 AC 4,241 ms
4,380 KB
testcase_14 AC 4,116 ms
4,376 KB
testcase_15 AC 4,264 ms
4,380 KB
testcase_16 AC 1,578 ms
4,380 KB
testcase_17 AC 1,127 ms
4,376 KB
testcase_18 AC 501 ms
4,384 KB
testcase_19 AC 2,687 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
struct num_info {
  int a;
  int lcm;
};
int gcd(int a, int b)
{
  int r;
  int ans;
  if (a < b) {
    r = b % a;
    while (r) {
      b = a;
      a = r;
      r = b % a;
    }
    ans = a;
  } else if (a > b) {
    r = a % b;
    while (r) {
      a = b;
      b = r;
      r = a % b;
    }
    ans = b;
  } else {
    ans = a;
  }
  return ans;
}
int search_min(struct num_info *A, int N)
{
  int i;
  int min = ~(1 << 31);
  int min_i;
  for (i=0; i<N; i++) {
    if (A[i].lcm < min) {
      min = A[i].lcm;
      min_i = i;
    } else if (A[i].lcm == min) {
      if (A[i].a < A[min_i].a) {
        min_i = i;
      }
    }
  }
  return min_i;
}
int main()
{
  int N;
  struct num_info *A;
  scanf("%d", &N);
  A = (struct num_info*)malloc(sizeof(struct num_info)*N);
  int i;
  for (i=0; i<N; i++) scanf("%d", &(A[i].a));

  if (N >= 3) {
    int j, k;
    for (i=0; i<N-2; i++) {
      for (j=i+1; j<N; j++) {
        A[j].lcm = A[i].a*A[j].a/gcd(A[i].a, A[j].a);
      }
      k = search_min(&(A[i+1]), N-(i+1));
      if (k > 0) {
        struct num_info W;
        W = A[i+1];
        A[i+1] = A[(i+1)+k];
        A[(i+1)+k] = W;
      }
    }
  }

  for (i=0; i<N-1; i++) printf("%d ", A[i].a);
  printf("%d\n", A[N-1].a);
  return 0;
}
0