結果

問題 No.2114 01 Matching
コンテスト
ユーザー chro_96
提出日時 2022-10-28 23:44:53
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,667 bytes
コンパイル時間 397 ms
コンパイル使用メモリ 30,592 KB
実行使用メモリ 6,696 KB
最終ジャッジ日時 2024-07-06 03:03:29
合計ジャッジ時間 7,276 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 27 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

int cmp_int_3d (const void *a, const void *b) {
  int *a_ = (int *)a;
  int *b_ = (int *)b;
  int idx = 0;
  
  while (idx < 3) {
    if (a_[idx] < b_[idx]) {
      return -1;
    }
    if (a_[idx] > b_[idx]) {
      return 1;
    }
    idx++;
  }
  
  return 0;
}

int main () {
  int n = 0;
  int m = 0;
  int k = 0;
  int b[400000] = {};
  int r[400000] = {};
  
  int res = 0;
  
  int *bs = NULL;
  int *rs = NULL;
  
  long long ans = 0LL;
  int bidx = 0;
  int ridx = 0;
  int is_ok = 1;
  
  res = scanf("%d", &n);
  res = scanf("%d", &m);
  res = scanf("%d", &k);
  for (int i = 0; i < n; i++) {
    res = scanf("%d", b+(2*i));
    b[2*i+1] = b[2*i]/k;
    b[2*i] %= k;
  }
  for (int i = 0; i < m; i++) {
    res = scanf("%d", r+(2*i));
    r[2*i+1] = r[2*i]/k;
    r[2*i] %= k;
  }
  
  if (m < n) {
    int tmp = m;
    m = n;
    n = tmp;
    bs = r;
    rs = b;
  } else {
    bs = b;
    rs = r;
  }
  
  qsort(bs, n, sizeof(int)*2, cmp_int_3d);
  qsort(rs, m, sizeof(int)*2, cmp_int_3d);
 
  while (bidx < n && is_ok > 0) {
    while (ridx < m && rs[2*ridx] < bs[2*bidx]) {
      ridx++;
    }
    if (ridx >= m || rs[2*ridx] > bs[2*bidx]) {
      is_ok = 0;
    } else {
      int bnidx = bidx;
      int rnidx = ridx;
      while (bnidx < n && bs[2*bidx] == bs[2*bnidx]) {
        bnidx++;
      }
      while (rnidx < m && rs[2*ridx] == rs[2*rnidx]) {
        rnidx++;
      }
      if (rnidx-ridx < bnidx-bidx) {
        is_ok = 0;
      } else {
      }
      bidx = bnidx;
      ridx = rnidx;
    } 
  }
  
  if (is_ok > 0) {
    printf("%lld\n", ans);
  } else {
    printf("-1\n");
  }
  
  return 0;
}
0