QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#815393#9880. Origami Warpucup-team087#TL 2971ms4248kbC++2317.2kb2024-12-15 13:49:092024-12-15 13:49:10

Judging History

你现在查看的是最新测评结果

  • [2024-12-15 13:49:10]
  • 评测
  • 测评结果:TL
  • 用时:2971ms
  • 内存:4248kb
  • [2024-12-15 13:49:09]
  • 提交

answer

#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else

// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;

template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
  vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

#define stoi stoll

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename T>
T floor(T a, T b) {
  return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
  return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
  return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
  T q = floor(x, y);
  return {q, x - q * y};
}

template <typename T, typename U>
T SUM(const vector<U> &A) {
  T sm = 0;
  for (auto &&a: A) sm += a;
  return sm;
}

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}
template <typename T>
T POP(pq<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(pqg<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  T a = que.back();
  que.pop_back();
  return a;
}

template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
  if (check_ok) assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
  FOR(iter) {
    double x = (ok + ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return (ok + ng) / 2;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
  vc<int> A(S.size());
  FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}

template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
  int N = A.size();
  vector<T> B(N + 1);
  FOR(i, N) { B[i + 1] = B[i] + A[i]; }
  if (off == 0) B.erase(B.begin());
  return B;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}

template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
  vc<T> &res = first;
  (res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "library/other/io.hpp"
#define FASTIO
#include <unistd.h>

// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;

struct Pre {
  char num[10000][4];
  constexpr Pre() : num() {
    for (int i = 0; i < 10000; i++) {
      int n = i;
      for (int j = 3; j >= 0; j--) {
        num[i][j] = n % 10 | '0';
        n /= 10;
      }
    }
  }
} constexpr pre;

inline void load() {
  memcpy(ibuf, ibuf + pil, pir - pil);
  pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
  pil = 0;
  if (pir < SZ) ibuf[pir++] = '\n';
}

inline void flush() {
  fwrite(obuf, 1, por, stdout);
  por = 0;
}

void rd(char &c) {
  do {
    if (pil + 1 > pir) load();
    c = ibuf[pil++];
  } while (isspace(c));
}

void rd(string &x) {
  x.clear();
  char c;
  do {
    if (pil + 1 > pir) load();
    c = ibuf[pil++];
  } while (isspace(c));
  do {
    x += c;
    if (pil == pir) load();
    c = ibuf[pil++];
  } while (!isspace(c));
}

template <typename T>
void rd_real(T &x) {
  string s;
  rd(s);
  x = stod(s);
}

template <typename T>
void rd_integer(T &x) {
  if (pil + 100 > pir) load();
  char c;
  do
    c = ibuf[pil++];
  while (c < '-');
  bool minus = 0;
  if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
    if (c == '-') { minus = 1, c = ibuf[pil++]; }
  }
  x = 0;
  while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
  if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
    if (minus) x = -x;
  }
}

void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }

template <class T, class U>
void rd(pair<T, U> &p) {
  return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
  if constexpr (N < std::tuple_size<T>::value) {
    auto &x = std::get<N>(t);
    rd(x);
    rd_tuple<N + 1>(t);
  }
}
template <class... T>
void rd(tuple<T...> &tpl) {
  rd_tuple(tpl);
}

template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
  for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
  for (auto &d: x) rd(d);
}

void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
  rd(h), read(t...);
}

void wt(const char c) {
  if (por == SZ) flush();
  obuf[por++] = c;
}
void wt(const string s) {
  for (char c: s) wt(c);
}
void wt(const char *s) {
  size_t len = strlen(s);
  for (size_t i = 0; i < len; i++) wt(s[i]);
}

template <typename T>
void wt_integer(T x) {
  if (por > SZ - 100) flush();
  if (x < 0) { obuf[por++] = '-', x = -x; }
  int outi;
  for (outi = 96; x >= 10000; outi -= 4) {
    memcpy(out + outi, pre.num[x % 10000], 4);
    x /= 10000;
  }
  if (x >= 1000) {
    memcpy(obuf + por, pre.num[x], 4);
    por += 4;
  } else if (x >= 100) {
    memcpy(obuf + por, pre.num[x] + 1, 3);
    por += 3;
  } else if (x >= 10) {
    int q = (x * 103) >> 10;
    obuf[por] = q | '0';
    obuf[por + 1] = (x - q * 10) | '0';
    por += 2;
  } else
    obuf[por++] = x | '0';
  memcpy(obuf + por, out + outi + 4, 96 - outi);
  por += 96 - outi;
}

template <typename T>
void wt_real(T x) {
  ostringstream oss;
  oss << fixed << setprecision(15) << double(x);
  string s = oss.str();
  wt(s);
}

void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }

template <class T, class U>
void wt(const pair<T, U> val) {
  wt(val.first);
  wt(' ');
  wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
  if constexpr (N < std::tuple_size<T>::value) {
    if constexpr (N > 0) { wt(' '); }
    const auto x = std::get<N>(t);
    wt(x);
    wt_tuple<N + 1>(t);
  }
}
template <class... T>
void wt(tuple<T...> tpl) {
  wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
  auto n = val.size();
  for (size_t i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(val[i]);
  }
}
template <class T>
void wt(const vector<T> val) {
  auto n = val.size();
  for (size_t i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(val[i]);
  }
}

void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  wt(head);
  if (sizeof...(Tail)) wt(' ');
  print(forward<Tail>(tail)...);
}

// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;

#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif

#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  read(__VA_ARGS__)
#define U32(...)   \
  u32 __VA_ARGS__; \
  read(__VA_ARGS__)
#define U64(...)   \
  u64 __VA_ARGS__; \
  read(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  read(__VA_ARGS__)
#define CHAR(...)   \
  char __VA_ARGS__; \
  read(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  read(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
void YA(bool t = 1) { print(t ? "YA" : "TIDAK"); }
void TIDAK(bool t = 1) { YES(!t); }
#line 3 "main.cpp"

#line 2 "library/random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 5 "main.cpp"

void solve() {
  LL(N);
  vi X, Y, ADD, SUB;
  bool origin = true;

  {
    vi A(N), B(N), C(N), D(N);
    FOR(i, N) read(A[i], B[i], C[i], D[i]);

    // X=c,Y=c,X+Y=c,X-Y=c

    FOR(i, N) {
      ll a = A[i], b = B[i], c = C[i], d = D[i];
      if (a * d != b * c) origin = false;

      if (a == c) X.eb(a);
      if (b == d) Y.eb(b);
      if (a + b == c + d) ADD.eb(a + b);
      if (a - b == c - d) SUB.eb(a - b);
    }
  }

  // UNIQUE(X);
  // UNIQUE(Y);
  // UNIQUE(ADD);
  // UNIQUE(SUB);
  SHOW(origin);

  bool irr = len(X) + len(Y) + len(ADD) + len(SUB) < N;
  SHOW(len(X), len(Y), len(ADD), len(SUB), irr);

  ll GX = 0;
  ll GY = 0;
  for (auto& x: X) GX = gcd(GX, x);
  for (auto& x: Y) GY = gcd(GY, x);

  auto solve_1_dim = [&](ll g, ll X1, ll X2) -> bool {
    // ll g = 0;
    // for (auto& x: X) g = gcd(g, x + x);
    if (g == 0) return X1 == X2 || X1 + X2 == 0;
    if ((X1 - X2) % (2 * g) == 0) return 1;
    if ((X1 + X2) % (2 * g) == 0) return 1;
    return 0;
  };

  vi A, B;
  concat(A, X, Y);
  concat(B, ADD, SUB);
  ll a = 0, b = 0;
  FOR(i, 1, len(A)) a = gcd(a, 2 * (A[i] - A[0]));
  FOR(i, 0, len(B)) b = gcd(b, 2 * B[i]);
  ll G = gcd(a, b);
  // 念のため?
  G *= 2;

  auto solve = [&](ll X1, ll Y1, ll X2, ll Y2) -> void {
    if (origin) {
      if (X1 * X1 + Y1 * Y1 != X2 * X2 + Y2 * Y2) return No();
      if (irr) return Yes();
      // 直線の個数は少ないし軌道も少ない
      set<pi> vis;
      vc<pi> que;
      auto upd = [&](ll x, ll y) -> void {
        pi p = {x, y};
        if (vis.count(p)) return;
        vis.insert(p);
        que.eb(x, y);
      };
      upd(X1, Y1);
      while (len(que)) {
        assert(len(vis) <= 16); // pm x, pm y
        auto [x, y] = POP(que);
        for (auto& c: X) upd(c + c - x, y);
        for (auto& c: Y) upd(x, c + c - y);
        // x+y==c
        for (auto& c: ADD) { upd(c - y, c - x); }
        // x-y==c
        for (auto& c: SUB) { upd(y + c, x - c); }
      }
      pi p = {X2, Y2};
      return Yes(vis.count(p));
    }
    if (irr) {
      // 無理数の角度がある
      // 原点をとおらないやつもある
      return Yes();
    }
    if (len(ADD) == 0 && len(SUB) == 0) { return Yes(solve_1_dim(GX, X1, X2) && solve_1_dim(GY, Y1, Y2)); }
    SHOW(G);
    ll trial = 100;
    FOR(trial) {
      ll x = X1, y = Y1;
      FOR(30) {
        bool ok_x = (x == X2 || (G != 0 && (x - X2) % G == 0));
        bool ok_y = (y == Y2 || (G != 0 && (y - Y2) % G == 0));
        if (ok_x && ok_y) return Yes();
        int t = RNG(0, 4);
        if (t == 0 && len(X)) {
          ll c = X[RNG(0, len(X))];
          tie(x, y) = mp(c + c - x, y);
        }
        if (t == 1 && len(Y)) {
          ll c = Y[RNG(0, len(Y))];
          tie(x, y) = mp(x, c + c - y);
        }
        if (t == 2 && len(ADD)) {
          ll c = ADD[RNG(0, len(ADD))];
          tie(x, y) = mp(c - y, c - x);
        }
        if (t == 3 && len(SUB)) {
          ll c = SUB[RNG(0, len(SUB))];
          tie(x, y) = mp(y + c, x - c);
        }
      }
    }
    return No();
  };

  LL(Q);
  FOR(Q) {
    LL(X1, Y1, X2, Y2);
    solve(X1, Y1, X2, Y2);
  }
}

signed main() {
  INT(T);
  FOR(T) solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3700kb

input:

2
3
0 0 1 0
0 0 0 1
0 2 2 0
4
1 0 2 3
1 -2 -1 2
1 1 -1 0
3 3 3 3
3
0 0 1 0
0 0 0 1
-2 1 2 3
2
2 1 -1 5
-1 -1 3 3

output:

Yes
Yes
No
Yes
Yes
Yes

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: 0
Accepted
time: 2ms
memory: 4136kb

input:

10
550
0 0 1 0
0 0 0 1
1070451 -76747419 -475756 34109964
39212129 -40187389 32082651 -32880591
-42770825 49053520 -51324990 58864224
301020 -10533714 602040 -21067428
-55137616 74952624 -24122707 32791773
1629975 -29851650 -478126 8756484
80523100 20960200 -77302176 -20121792
-64028006 61179727 -18...

output:

Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Ye...

result:

ok 12244 token(s): yes count is 6128, no count is 6116

Test #3:

score: 0
Accepted
time: 18ms
memory: 3936kb

input:

100
2000
0 0 1 0
0 0 0 1
-84998108 27087723 -78459792 25004052
-63732795 -93286980 29741971 43533924
88160702 10753904 -94457895 -11522040
-57759240 -99131840 25991658 44609328
-35408095 31386545 -92061047 81605017
21178080 37382229 32943680 58150134
-57187533 84956404 -17596164 26140432
38432164 17...

output:

No
No
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
No
No
Yes
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
N...

result:

ok 200000 token(s): yes count is 100141, no count is 99859

Test #4:

score: 0
Accepted
time: 2971ms
memory: 4000kb

input:

90
1025
0 0 1 0
0 0 0 1
-8716657 -748858 12990792 -22456307
-13593063 -23283552 -46628353 -23283552
93002789 28574481 93002789 78693002
-16042487 47828662 -30013237 61799412
43359811 68260568 43359811 -75987953
-94388305 52022201 -94388305 8537759
-6363687 -1383673 -6363687 -20211179
-29739675 -2602...

output:

Yes
No
No
No
Yes
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
No
N...

result:

ok 111911 token(s): yes count is 30198, no count is 81713

Test #5:

score: 0
Accepted
time: 2244ms
memory: 3976kb

input:

60
1827
0 0 1 0
0 0 0 1
-17538300 -17990820 -3024627 -3477147
1931426 28295794 -7230316 37457536
-50091040 -61102720 -50091040 -81287891
-8748721 7610399 -3122974 13236146
-11031224 10681644 26710340 -27059920
24141834 -4020934 30472616 -10351716
-34145900 53640301 -34145900 50102047
-9267760 282286...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Ye...

result:

ok 72683 token(s): yes count is 7452, no count is 65231

Test #6:

score: 0
Accepted
time: 2468ms
memory: 4200kb

input:

60
1997
0 0 1 0
0 0 0 1
69327545 -42290317 69327545 63981221
-58631846 -15683378 -58631846 18914662
4797598 12519123 -29048979 46365700
9216180 2556055 20722330 -8950095
-36543647 35024712 -35771895 35024712
-10489112 91685408 -10489112 -57484395
6794531 26436588 6794531 -20764239
-26423402 -4976896...

output:

Yes
No
No
Yes
Yes
No
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
No
Yes
No
No
No
No
No
Yes
No
Yes
Yes
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
Yes
Yes
No
No
Yes
Yes
No
No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
No
Yes
No
No
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
Yes
Yes
N...

result:

ok 79849 token(s): yes count is 8192, no count is 71657

Test #7:

score: 0
Accepted
time: 1909ms
memory: 4248kb

input:

60
807
0 0 1 0
0 0 0 1
69990110 52698324 58640751 52698324
-6015050 2800994 -4061102 4754942
67806960 -10866065 67806960 78717943
-66237090 -99083936 83175963 -99083936
-89057656 -95080370 64126205 -95080370
-74320306 14980336 61936095 14980336
-4691148 24838238 -13069432 33216522
-44184536 34829110...

output:

Yes
Yes
Yes
Yes
No
No
No
No
Yes
No
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
No
No
Yes
No
No
Yes
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
No
Yes
No
No...

result:

ok 71776 token(s): yes count is 21769, no count is 50007

Test #8:

score: 0
Accepted
time: 1980ms
memory: 4044kb

input:

60
1891
0 0 1 0
0 0 0 1
-9198393 -8883107 31549745 -49631245
11096271 -8799824 34381579 -8799824
79393665 44942616 5266446 44942616
80038104 59629280 80038104 -73960991
59670664 95699832 59670664 -81538173
-73541249 -26052008 -16573483 -26052008
60296113 60318720 60104916 60318720
46427576 8929327 4...

output:

Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
...

result:

ok 72035 token(s): yes count is 14238, no count is 57797

Test #9:

score: 0
Accepted
time: 1487ms
memory: 4092kb

input:

55
682
0 0 1 0
0 0 0 1
-17023944 6375984 -32126895 21478935
-8975753 -17499359 -25464803 -1010309
-29768060 -42931964 2968852 -10195052
20010198 8113370 21431358 6692210
-10855708 -19806860 -30869619 207051
10554553 1985831 -11026795 23567179
21880938 -5953302 -28304390 -56138630
7753068 -29186348 -...

output:

No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 69726 token(s): yes count is 15879, no count is 53847

Test #10:

score: -100
Time Limit Exceeded

input:

100
2000
0 0 1 0
0 0 0 1
11659007 -12317071 21489140 -2486938
-82315139 90329884 -29802604 90329884
53186946 50733878 53186946 41692310
-26440204 65035919 -26440204 -65223934
7444254 -6850298 -10866206 -25160758
23235570 -41755929 -27157227 8636868
38843792 -25255333 51413751 -25255333
-95459342 741...

output:

No
Yes
No
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
No
No
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
Yes...

result: