結果

問題 No.14 最小公倍数ソート
コンテスト
ユーザー mudbdb
提出日時 2015-06-25 22:33:24
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 3,713 ms / 5,000 ms
コード長 1,289 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 22,272 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-07 17:38:45
合計ジャッジ時間 41,823 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:53:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |   scanf("%d", &N);
      |   ^~~~~~~~~~~~~~~
main.c:56:23: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |   for (i=0; i<N; i++) scanf("%d", &(A[i].a));
      |                       ^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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