結果

問題 No.511 落ちゲー 〜手作業のぬくもり〜
ユーザー te-shte-sh
提出日時 2018-01-24 16:16:01
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 194 ms / 4,000 ms
コード長 2,157 bytes
コンパイル時間 2,740 ms
コンパイル使用メモリ 156,108 KB
実行使用メモリ 27,120 KB
最終ジャッジ日時 2023-09-03 18:14:17
合計ジャッジ時間 5,907 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 3 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 3 ms
4,376 KB
testcase_28 AC 4 ms
4,376 KB
testcase_29 AC 194 ms
24,508 KB
testcase_30 AC 187 ms
24,920 KB
testcase_31 AC 124 ms
24,780 KB
testcase_32 AC 152 ms
24,640 KB
testcase_33 AC 73 ms
14,800 KB
testcase_34 AC 61 ms
8,620 KB
testcase_35 AC 186 ms
26,152 KB
testcase_36 AC 187 ms
27,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.typecons;  // Tuple, Nullable, BigFlags

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
T[] readArray(T)(size_t n){auto a=new T[](n),r=readln.splitter;foreach(ref v;a){v=r.front.to!T;r.popFront;}return a;}
T[] readArrayM(T)(size_t n){auto a=new T[](n);foreach(ref v;a)v=readln.chomp.to!T;return a;}

void main()
{
  int n, w; long h; readV(n, w, h);
  auto a = new int[](n), b = new int[](n), x = new int[](n);
  foreach (i; 0..n) {
    readV(a[i], b[i], x[i]); --x[i];
  }

  auto isExceed(int t, int[] c)
  {
    auto s = new long[](w+1);
    foreach (ai, bi, xi; lockstep(a[0..t], b[0..t], x[0..t])) {
      s[xi] += bi;
      s[xi+ai] -= bi;
    }
    foreach (i; 1..w) s[i] = s[i-1]+s[i];
    auto r = new bool[](c.length);
    foreach (i, ci; c) r[i] = s[ci] >= h;
    return r;
  }

  auto separateC(int[] c, bool[] r)
  {
    int[] f, t;
    foreach (ci, ri; lockstep(c, r)) {
      if (ri) t ~= ci;
      else    f ~= ci;
    }
    return tuple(f, t);
  }

  auto mergeC(int[] c1, int[] t1, int[] c2, int[] t2)
  {
    auto n1 = c1.length, n2 = c2.length;
    auto t = new int[](n1+n2), i = 0, i1 = 0, i2 = 0;
    while (i < n1+n2) {
      if (i1 >= n1)             t[i++] = t2[i2++];
      else if (i2 >= n2)        t[i++] = t1[i1++];
      else if (c1[i1] < c2[i2]) t[i++] = t1[i1++];
      else                      t[i++] = t2[i2++];
    }
    return t;
  }

  int[] bsearch(int mi, int ma, int[] c)
  {
    if (c.empty) return [];
    if (ma-mi <= 1) {
      auto r = isExceed(mi, c);
      auto t = new int[](c.length);
      foreach (ci, ref ti, ri; lockstep(c, t, r)) ti = ri ? mi : ma;
      return t;
    } else {
      auto ce = (mi+ma)/2, r = isExceed(ce, c);
      auto cs = separateC(c, r), c1 = cs[0], c2 = cs[1];
      auto t1 = bsearch(ce, ma, c1);
      auto t2 = bsearch(mi, ce, c2);
      return mergeC(c1, t1, c2, t2);
    }
  }

  auto t = bsearch(0, n, iota(0, w).array);

  auto p = new int[](2);
  foreach (ti; t) ++p[ti%2];

  writeln(p[0] == p[1] ? "DRAW" : p[0] < p[1] ? "A" : "B");
}
0