Submission #21284863


Source Code Expand

Copy
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }




void main() {
  try {
    for (; ; ) {
      const numCases = readInt();
      foreach (caseId; 0 .. numCases) {
        const M = readInt();
        const N = readInt();
        auto A = new long[M];
        foreach (i; 0 .. M) {
          A[i] = readLong();
        }
        auto B = new long[N];
        foreach (j; 0 .. N) {
          B[j] = readLong();
        }
        A.sort;
        B.sort;
        
        BinaryHeap!(Array!long) que;
        foreach (j; 0 .. N) {
          que.insert(B[j]);
        }
        bool ans = true;
        int cnt = N;
        foreach_reverse (i; 0 .. M) {
          for (; ; ) {
            long b = que.front;
            que.removeFront;
            if ((i == 0 || !que.empty) && A[i] >= b) {
              break;
            }
            que.insert(b / 2);
            que.insert(b - b / 2);
            if (++cnt > M) {
              ans = false;
              break;
            }
          }
        }
        ans = ans && que.empty;
        writeln(ans ? "Yes" : "No");
        
        debug {
          bool dfs(long[] as) {
            as.sort;
            const len = cast(int)(as.length);
            if (len == N) {
              bool ok = true;
              foreach (j; 0 .. N) {
                ok = ok && (as[j] >= B[j]);
              }
              return ok;
            } else {
              foreach (i0; 0 .. len) foreach (i1; i0 + 1 .. len) {
                long[] aas;
                foreach (i; 0 .. len) {
                  if (i != i0 && i != i1) {
                    aas ~= as[i];
                  }
                }
                aas ~= as[i0] + min(as[i0] + 1, as[i1]);
                if (dfs(aas)) {
                  return true;
                }
              }
              return false;
            }
          }
          const brt = dfs(A.dup);
          assert(brt == ans, format("A = %s, B = %s: %s %s", A, B, brt, ans));
        }
      }
    }
  } catch (EOFException e) {
  }
}

Submission Info

Submission Time
Task J - Merge and Decrement
User hos_lyric
Language D (LDC 1.20.1)
Score 100
Code Size 3247 Byte
Status AC
Exec Time 100 ms
Memory 11824 KB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 41
Set Name Test Cases
sample 00_sample_00
All 00_sample_00, 01_small_00, 01_small_01, 01_small_02, 01_small_03, 01_small_04, 01_small_05, 01_small_06, 01_small_07, 01_small_08, 01_small_09, 02_medium_00, 02_medium_01, 02_medium_02, 02_medium_03, 02_medium_04, 02_medium_05, 02_medium_06, 03_large_00, 03_large_01, 03_large_02, 03_large_03, 03_large_04, 03_large_05, 03_large_06, 04_verylarge_00, 04_verylarge_01, 04_verylarge_02, 04_verylarge_03, 04_verylarge_04, 04_verylarge_05, 04_verylarge_06, 05_all_00, 05_all_01, 05_all_02, 05_all_03, 05_all_04, 05_all_05, 05_all_06, 06_corner_00, 06_corner_01
Case Name Status Exec Time Memory
00_sample_00 AC 8 ms 3380 KB
01_small_00 AC 75 ms 4116 KB
01_small_01 AC 78 ms 3860 KB
01_small_02 AC 78 ms 3852 KB
01_small_03 AC 79 ms 4112 KB
01_small_04 AC 82 ms 4284 KB
01_small_05 AC 79 ms 3896 KB
01_small_06 AC 79 ms 3800 KB
01_small_07 AC 78 ms 4132 KB
01_small_08 AC 79 ms 4064 KB
01_small_09 AC 78 ms 4232 KB
02_medium_00 AC 68 ms 3844 KB
02_medium_01 AC 68 ms 3948 KB
02_medium_02 AC 71 ms 3916 KB
02_medium_03 AC 65 ms 3884 KB
02_medium_04 AC 67 ms 3964 KB
02_medium_05 AC 64 ms 3952 KB
02_medium_06 AC 69 ms 3876 KB
03_large_00 AC 80 ms 7848 KB
03_large_01 AC 79 ms 7948 KB
03_large_02 AC 80 ms 7984 KB
03_large_03 AC 84 ms 7800 KB
03_large_04 AC 83 ms 7940 KB
03_large_05 AC 83 ms 7884 KB
03_large_06 AC 79 ms 7924 KB
04_verylarge_00 AC 98 ms 8480 KB
04_verylarge_01 AC 100 ms 8428 KB
04_verylarge_02 AC 98 ms 11824 KB
04_verylarge_03 AC 97 ms 8152 KB
04_verylarge_04 AC 100 ms 8396 KB
04_verylarge_05 AC 95 ms 7872 KB
04_verylarge_06 AC 97 ms 8244 KB
05_all_00 AC 67 ms 3996 KB
05_all_01 AC 72 ms 4400 KB
05_all_02 AC 67 ms 3896 KB
05_all_03 AC 66 ms 3848 KB
05_all_04 AC 64 ms 3896 KB
05_all_05 AC 69 ms 4144 KB
05_all_06 AC 68 ms 4144 KB
06_corner_00 AC 14 ms 3840 KB
06_corner_01 AC 10 ms 3940 KB