QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726383#7680. SubwaymaspyAC ✓1ms4120kbC++2319.1kb2024-11-08 23:29:362024-11-08 23:29:37

Judging History

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

  • [2024-11-08 23:29:37]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4120kb
  • [2024-11-08 23:29:36]
  • 提交

answer

#line 1 "/home/maspy/compro/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(x) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parity(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 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 "/home/maspy/compro/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); }
#line 3 "main.cpp"

#line 2 "/home/maspy/compro/library/geo/base.hpp"
template <typename T>
struct Point {
  T x, y;

  Point() : x(0), y(0) {}

  template <typename A, typename B>
  Point(A x, B y) : x(x), y(y) {}

  template <typename A, typename B>
  Point(pair<A, B> p) : x(p.fi), y(p.se) {}

  Point operator+=(const Point p) {
    x += p.x, y += p.y;
    return *this;
  }
  Point operator-=(const Point p) {
    x -= p.x, y -= p.y;
    return *this;
  }
  Point operator+(Point p) const { return {x + p.x, y + p.y}; }
  Point operator-(Point p) const { return {x - p.x, y - p.y}; }
  bool operator==(Point p) const { return x == p.x && y == p.y; }
  bool operator!=(Point p) const { return x != p.x || y != p.y; }
  Point operator-() const { return {-x, -y}; }
  Point operator*(T t) const { return {x * t, y * t}; }
  Point operator/(T t) const { return {x / t, y / t}; }

  bool operator<(Point p) const {
    if (x != p.x) return x < p.x;
    return y < p.y;
  }
  T dot(const Point& other) const { return x * other.x + y * other.y; }
  T det(const Point& other) const { return x * other.y - y * other.x; }

  double norm() { return sqrtl(x * x + y * y); }
  double angle() { return atan2(y, x); }

  Point rotate(double theta) {
    static_assert(!is_integral<T>::value);
    double c = cos(theta), s = sin(theta);
    return Point{c * x - s * y, s * x + c * y};
  }
  Point rot90(bool ccw) { return (ccw ? Point{-y, x} : Point{y, -x}); }
};

#ifdef FASTIO
template <typename T>
void rd(Point<T>& p) {
  fastio::rd(p.x), fastio::rd(p.y);
}
template <typename T>
void wt(Point<T>& p) {
  fastio::wt(p.x);
  fastio::wt(' ');
  fastio::wt(p.y);
}
#endif

// A -> B -> C と進むときに、左に曲がるならば +1、右に曲がるならば -1
template <typename T>
int ccw(Point<T> A, Point<T> B, Point<T> C) {
  T x = (B - A).det(C - A);
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;
}

template <typename REAL, typename T, typename U>
REAL dist(Point<T> A, Point<U> B) {
  REAL dx = REAL(A.x) - REAL(B.x);
  REAL dy = REAL(A.y) - REAL(B.y);
  return sqrt(dx * dx + dy * dy);
}

// ax+by+c
template <typename T>
struct Line {
  T a, b, c;

  Line(T a, T b, T c) : a(a), b(b), c(c) {}
  Line(Point<T> A, Point<T> B) { a = A.y - B.y, b = B.x - A.x, c = A.x * B.y - A.y * B.x; }
  Line(T x1, T y1, T x2, T y2) : Line(Point<T>(x1, y1), Point<T>(x2, y2)) {}

  template <typename U>
  U eval(Point<U> P) {
    return a * P.x + b * P.y + c;
  }

  template <typename U>
  T eval(U x, U y) {
    return a * x + b * y + c;
  }

  // 同じ直線が同じ a,b,c で表現されるようにする
  void normalize() {
    static_assert(is_same_v<T, int> || is_same_v<T, long long>);
    T g = gcd(gcd(abs(a), abs(b)), abs(c));
    a /= g, b /= g, c /= g;
    if (b < 0) { a = -a, b = -b, c = -c; }
    if (b == 0 && a < 0) { a = -a, b = -b, c = -c; }
  }

  bool is_parallel(Line other) { return a * other.b - b * other.a == 0; }
  bool is_orthogonal(Line other) { return a * other.a + b * other.b == 0; }
};

template <typename T>
struct Segment {
  Point<T> A, B;

  Segment(Point<T> A, Point<T> B) : A(A), B(B) {}
  Segment(T x1, T y1, T x2, T y2) : Segment(Point<T>(x1, y1), Point<T>(x2, y2)) {}

  bool contain(Point<T> C) {
    T det = (C - A).det(B - A);
    if (det != 0) return 0;
    return (C - A).dot(B - A) >= 0 && (C - B).dot(A - B) >= 0;
  }

  Line<T> to_Line() { return Line(A, B); }
};

template <typename REAL>
struct Circle {
  Point<REAL> O;
  REAL r;
  Circle(Point<REAL> O, REAL r) : O(O), r(r) {}
  Circle(REAL x, REAL y, REAL r) : O(x, y), r(r) {}
  template <typename T>
  bool contain(Point<T> p) {
    REAL dx = p.x - O.x, dy = p.y - O.y;
    return dx * dx + dy * dy <= r * r;
  }
};
#line 2 "/home/maspy/compro/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 6 "main.cpp"

/*
ある直線との内積について distinct にする
間の点もとれるようにする
直交方向に50個ずつ点をとる, あるならそこから
*/

using P = Point<ll>;

void solve() {
  LL(N);
  vc<P> A(N);
  vi B(N);
  FOR(i, N) read(A[i], B[i]);

  vi dot(N);
  P p, q;

  while (1) {
    p.x = RNG(1, 1000);
    p.y = RNG(1, 1000);
    if (gcd(p.x, p.y) > 1) continue;
    q = p.rot90(true);
    FOR(i, N) dot[i] = A[i].dot(p);
    auto I = argsort(dot);

    dot = rearrange(dot, I);
    A = rearrange(A, I);
    B = rearrange(B, I);
    bool ok = 1;
    FOR(i, len(dot) - 1) if (dot[i + 1] <= dot[i] + 1) ok = 0;
    if (ok) break;
  }
  ll n = MAX(B);

  auto gen = [&](ll d) -> vc<P> {
    vc<P> ANS;
    int k = LB(dot, d);
    if (k < len(dot) && dot[k] == d) {
      ANS.eb(A[k]);
    } else {
      ll a = p.x, b = p.y;
      auto [x, y] = [&]() -> pi {
        FOR(x, 1 << 20) {
          ll y = (d - a * x) / b;
          if (a * x + b * y == d) return {x, y};
        }
        assert(0);
        return {0, 0};
      }();
      ANS.eb(x, y);
    }
    FOR(n - 1) ANS.eb(ANS.back() + q);
    return ANS;
  };

  vv(P, ANS, n, 2 * N);
  FOR(i, N) {
    ll c = dot[i];
    auto point = gen(c - 1);
    FOR(k, n) ANS[k][2 * i + 0] = point[k];
  }
  FOR(i, N) {
    ll c = dot[i];
    auto point = gen(c);
    FOR(k, n) {
      ANS[k][2 * i + 1] = point[k];
      if (k < B[i]) ANS[k][2 * i + 1] = point[0];
    }
  }
  print(n);
  FOR(i, n) {
    vi out;
    out.eb(len(ANS[i]));
    for (auto& p: ANS[i]) out.eb(p.x), out.eb(p.y);
    print(out);
  }
}

signed main() { solve(); }

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 2 1
2 1 2
3 3 2

output:

2
6 158 -157 1 2 159 -158 2 1 160 -156 3 3
6 -78 82 -235 241 -77 81 2 1 -76 83 3 3

result:

ok ok Sum L = 12

Test #2:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

1
1 1 1

output:

1
2 258 -77 1 1

result:

ok ok Sum L = 2

Test #3:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

1
1 1 50

output:

50
2 714 -819 1 1
2 -19 24 1 1
2 -752 867 1 1
2 -1485 1710 1 1
2 -2218 2553 1 1
2 -2951 3396 1 1
2 -3684 4239 1 1
2 -4417 5082 1 1
2 -5150 5925 1 1
2 -5883 6768 1 1
2 -6616 7611 1 1
2 -7349 8454 1 1
2 -8082 9297 1 1
2 -8815 10140 1 1
2 -9548 10983 1 1
2 -10281 11826 1 1
2 -11014 12669 1 1
2 -11747 1...

result:

ok ok Sum L = 100

Test #4:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

50
662 -567 48
728 -120 7
307 669 27
-885 -775 21
100 242 9
-784 -537 41
940 198 46
736 -551 30
-449 456 16
-945 382 18
-182 810 49
213 187 44
853 245 48
617 -305 19
-81 261 3
617 208 8
-548 -652 6
-888 -667 14
-371 -812 43
202 -702 10
-668 -725 5
961 -919 33
-870 -697 50
428 810 29
560 405 7
348 -3...

output:

50
100 551 -1874 -885 -775 566 -1796 -870 -697 548 -1766 -888 -667 1 -1237 -668 -725 652 -1636 -784 -537 363 -1409 -306 -897 298 -1324 -371 -812 207 -1231 -462 -719 121 -1164 -548 -652 455 -1292 -981 -193 90 -949 -579 -437 236 -818 334 -893 200 -768 -469 -256 170 -689 -499 -177 104 -627 202 -702 491...

result:

ok ok Sum L = 5000

Test #5:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

50
-772 697 1
-756 -909 1
659 923 1
850 471 1
260 -24 1
473 -639 1
-575 393 1
-466 197 1
333 -637 1
-192 -890 1
103 546 1
749 -723 1
-573 613 1
214 -138 1
277 928 1
266 291 1
911 275 1
-680 -67 1
69 190 1
-197 -795 1
684 618 1
729 -115 1
-658 -229 1
-595 -470 1
898 -172 1
401 81 1
133 685 1
223 400 ...

output:

1
100 308 -1822 -756 -909 493 -1629 -571 -716 141 -1219 -162 -959 111 -1150 -192 -890 469 -1383 -595 -470 106 -1055 -197 -795 30 -932 -273 -672 87 -971 -216 -711 333 -1129 30 -869 406 -1142 -658 -229 398 -995 -666 -82 384 -980 -680 -67 168 -769 -135 -509 636 -897 333 -637 663 -890 360 -630 15 -246 4...

result:

ok ok Sum L = 100

Test #6:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

50
-56 747 3
993 -490 4
930 -139 1
-298 -330 1
938 -351 5
-973 100 5
-472 44 4
345 628 5
481 -91 4
789 581 5
457 -29 4
871 -799 1
692 994 4
699 854 2
893 -33 1
-483 256 3
-962 -540 2
846 -893 1
830 609 5
845 -383 2
-552 -966 1
-544 -51 1
564 186 4
-615 -675 1
618 -911 3
-561 -302 4
-293 667 3
-334 -...

output:

5
100 269 -1419 -552 -966 184 -1254 -637 -801 783 -1535 -888 -613 709 -1462 -962 -540 29 -1078 -792 -625 206 -1128 -615 -675 327 -970 356 -986 319 -959 348 -975 838 -1210 17 -757 487 -988 -334 -535 260 -755 -561 -302 589 -895 618 -911 588 -885 -233 -432 565 -831 594 -847 523 -783 -298 -330 698 -822 ...

result:

ok ok Sum L = 500

Test #7:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

50
600 997 5
-893 -204 3
408 443 1
-560 -748 7
-647 161 6
-285 -980 1
87 -582 7
-48 -721 7
997 285 2
-189 -728 8
525 222 4
-324 816 9
760 317 3
753 -480 10
-813 -921 3
-325 -875 8
-747 816 10
-627 605 7
775 786 6
136 -54 2
274 948 10
216 -113 7
924 68 3
101 576 8
60 -501 2
898 801 8
-767 -974 10
-99...

output:

10
100 29 -2230 -813 -921 75 -2283 -767 -974 108 -1991 -972 -312 98 -1891 -982 -212 44 -1687 -560 -748 68 -1698 -893 -204 37 -1613 -805 -304 53 -1565 -313 -996 81 -1549 -285 -980 41 -1444 -325 -875 63 -1459 -660 -335 88 -1495 -397 -741 108 -1507 -258 -938 106 -1397 -498 -458 88 -1167 -278 -598 58 -1...

result:

ok ok Sum L = 1000

Test #8:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

50
24 -889 49
117 418 49
25 524 44
980 -416 43
-494 357 41
-287 -285 46
151 574 41
-289 68 49
-515 -540 41
-367 -178 47
-887 151 45
197 -272 47
714 724 45
-737 94 49
810 830 47
808 -695 41
537 -637 49
-142 -167 44
-749 -631 47
445 -444 42
801 910 43
59 363 42
-912 466 50
-649 -479 48
-958 -511 49
88...

output:

50
100 235 -4036 -958 -511 201 -3438 -749 -631 164 -3191 -786 -384 82 -2921 -868 -114 195 -3182 -998 343 63 -2656 -887 151 58 -2568 -649 -479 38 -2341 -912 466 213 -2713 -737 94 192 -2629 -515 -540 119 -2227 -588 -138 182 -2288 -282 -917 97 -1549 -367 -178 177 -1656 -287 -285 213 -1732 -494 357 92 -...

result:

ok ok Sum L = 5000

Test #9:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

50
151 -171 50
-367 -951 50
808 569 50
150 -618 50
27 -476 50
-846 729 50
549 -456 50
50 646 50
294 -70 50
-571 104 50
128 -265 50
913 -700 50
267 -965 50
896 846 50
-2 713 50
21 679 50
-515 975 50
168 180 50
-369 -98 50
676 115 50
643 -779 50
920 -237 50
-324 450 50
149 -378 50
-882 -602 50
-126 -7...

output:

50
100 269 -1066 -302 -989 204 -1028 -367 -951 178 -953 267 -965 108 -911 197 -923 328 -932 417 -944 445 -876 -126 -799 392 -861 481 -873 349 -768 -882 -602 554 -767 643 -779 61 -606 150 -618 164 -599 913 -700 409 -624 498 -636 598 -553 27 -476 146 -463 895 -564 332 -451 421 -463 378 -447 -193 -370 ...

result:

ok ok Sum L = 5000

Test #10:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

50
4 5 34
1 -5 24
-4 -4 32
-3 3 28
0 -1 21
1 -4 25
0 0 30
0 -4 42
-3 -2 44
-5 -3 37
4 -1 46
5 2 20
2 2 37
-2 5 35
-2 -1 39
2 4 32
-4 -3 42
0 3 32
3 5 47
-4 1 2
5 -1 17
-5 -4 5
-2 2 29
-5 1 11
2 -5 43
4 4 14
-5 0 9
0 -5 17
5 1 27
-3 0 24
-1 4 16
5 0 50
3 -2 18
1 -2 6
2 -1 29
-1 3 38
1 5 36
-3 1 28
-3...

output:

50
100 257 -17 -2 -5 259 -17 0 -5 260 -17 1 -5 261 -17 2 -5 254 -16 -5 -4 255 -16 -4 -4 258 -16 -1 -4 259 -16 0 -4 260 -16 1 -4 264 -16 5 -4 254 -15 -5 -3 255 -15 -4 -3 256 -15 -3 -3 259 -15 0 -3 261 -15 2 -3 256 -14 -3 -2 259 -14 0 -2 260 -14 1 -2 262 -14 3 -2 256 -13 -3 -1 257 -13 -2 -1 259 -13 0 ...

result:

ok ok Sum L = 5000

Test #11:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

50
2 0 2
2 -3 2
4 1 2
-3 -3 2
-5 1 2
5 3 2
-5 -3 2
-3 -2 2
2 -1 2
2 3 2
4 4 1
1 -4 1
5 -1 2
-4 1 2
3 -2 1
-1 2 2
5 -5 2
-2 1 2
-5 -1 2
-2 -1 2
-1 -2 2
5 5 1
0 -2 2
1 1 1
2 2 2
3 5 2
-2 -4 1
-3 5 1
4 2 2
-4 -4 2
-3 2 1
5 0 2
-2 -2 2
-4 4 1
-2 5 2
2 5 1
3 -5 2
-4 5 2
-5 5 2
-2 4 2
-5 -5 2
-2 2 2
-3 -4...

output:

2
100 57 -66 -5 -5 58 -65 -4 -4 57 -64 -5 -3 59 -65 -3 -4 60 -65 -2 -4 59 -64 -3 -3 57 -62 -5 -1 61 -65 -1 -4 59 -63 -3 -2 60 -63 -2 -2 57 -60 -5 1 63 -65 1 -4 61 -63 -1 -2 60 -62 -2 -1 59 -61 -3 0 58 -60 -4 1 65 -66 3 -5 64 -65 2 -4 62 -63 0 -2 64 -64 2 -3 63 -63 1 -2 62 -62 0 -1 60 -60 -2 1 59 -59...

result:

ok ok Sum L = 200

Test #12:

score: 0
Accepted
time: 1ms
memory: 3880kb

input:

50
4 3 49
-5 -3 49
0 -3 50
-2 -4 49
-5 -5 50
4 0 49
-1 -2 49
-2 0 49
1 2 50
-1 -5 50
-5 -1 50
-5 5 49
2 0 50
-2 -3 50
-4 -5 50
0 -2 50
-5 4 50
-1 1 49
-1 -4 49
-3 -1 49
1 -3 50
-4 1 50
0 5 50
1 -2 50
-1 5 50
4 2 50
4 -3 49
1 -4 49
-1 -1 49
-3 -5 50
4 -4 50
3 2 49
3 -3 49
0 2 50
-3 -4 49
5 -1 49
-3 5...

output:

50
100 217 -66 -5 -5 218 -66 -4 -5 219 -66 -3 -5 221 -66 -1 -5 219 -65 -3 -4 223 -66 1 -5 220 -65 -2 -4 224 -66 2 -5 217 -64 -5 -3 221 -65 -1 -4 222 -65 0 -4 223 -65 1 -4 220 -64 -2 -3 222 -64 0 -3 226 -65 4 -4 223 -64 1 -3 217 -62 -5 -1 221 -63 -1 -2 225 -64 3 -3 222 -63 0 -2 226 -64 4 -3 219 -62 -...

result:

ok ok Sum L = 5000

Test #13:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

50
114 514 30
115 514 41
116 514 6
117 514 49
118 514 10
119 514 49
120 514 1
121 514 7
122 514 3
123 514 4
124 514 1
125 514 12
126 514 15
127 514 16
128 514 34
129 514 24
130 514 49
131 514 43
132 514 25
133 514 12
134 514 26
135 514 13
136 514 12
137 514 15
138 514 7
139 514 25
140 514 5
141 514 ...

output:

49
100 98 551 114 514 99 551 115 514 100 551 116 514 101 551 117 514 102 551 118 514 103 551 119 514 104 551 120 514 105 551 121 514 106 551 122 514 107 551 123 514 108 551 124 514 109 551 125 514 110 551 126 514 111 551 127 514 112 551 128 514 113 551 129 514 114 551 130 514 115 551 131 514 116 551...

result:

ok ok Sum L = 4900

Test #14:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

50
191 981 19
191 980 41
191 979 20
191 978 14
191 977 2
191 976 49
191 975 40
191 974 3
191 973 20
191 972 6
191 971 13
191 970 4
191 969 4
191 968 47
191 967 32
191 966 11
191 965 34
191 964 30
191 963 3
191 962 16
191 961 24
191 960 30
191 959 34
191 958 31
191 957 24
191 956 29
191 955 42
191 95...

output:

49
100 151 1021 191 932 151 1022 191 933 151 1023 191 934 151 1024 191 935 151 1025 191 936 151 1026 191 937 151 1027 191 938 151 1028 191 939 151 1029 191 940 151 1030 191 941 151 1031 191 942 151 1032 191 943 151 1033 191 944 151 1034 191 945 151 1035 191 946 151 1036 191 947 151 1037 191 948 151 ...

result:

ok ok Sum L = 4900

Test #15:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

50
-123 456 47
-122 457 35
-121 458 25
-120 459 35
-119 460 30
-118 461 33
-117 462 21
-116 463 31
-115 464 21
-114 465 35
-113 466 20
-112 467 17
-111 468 25
-110 469 3
-109 470 29
-108 471 35
-107 472 4
-106 473 44
-105 474 4
-104 475 28
-103 476 49
-102 477 9
-101 478 39
-100 479 9
-99 480 21
-98...

output:

50
100 228 -250 -123 456 229 -249 -122 457 230 -248 -121 458 231 -247 -120 459 232 -246 -119 460 233 -245 -118 461 234 -244 -117 462 235 -243 -116 463 236 -242 -115 464 237 -241 -114 465 238 -240 -113 466 239 -239 -112 467 240 -238 -111 468 241 -237 -110 469 242 -236 -109 470 243 -235 -108 471 244 -...

result:

ok ok Sum L = 5000

Test #16:

score: 0
Accepted
time: 1ms
memory: 4120kb

input:

50
321 -525 46
322 -526 14
323 -527 16
324 -528 38
325 -529 22
326 -530 24
327 -531 48
328 -532 5
329 -533 7
330 -534 30
331 -535 25
332 -536 2
333 -537 13
334 -538 1
335 -539 33
336 -540 8
337 -541 9
338 -542 2
339 -543 29
340 -544 17
341 -545 41
342 -546 39
343 -547 9
344 -548 47
345 -549 47
346 -...

output:

50
100 290 -493 321 -525 291 -494 322 -526 292 -495 323 -527 293 -496 324 -528 294 -497 325 -529 295 -498 326 -530 296 -499 327 -531 297 -500 328 -532 298 -501 329 -533 299 -502 330 -534 300 -503 331 -535 301 -504 332 -536 302 -505 333 -537 303 -506 334 -538 304 -507 335 -539 305 -508 336 -540 306 -...

result:

ok ok Sum L = 5000

Test #17:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

50
-444 -555 23
-445 -556 32
-446 -557 36
-447 -558 29
-448 -559 4
-449 -560 25
-450 -561 29
-451 -562 5
-452 -563 9
-453 -564 28
-454 -565 35
-455 -566 26
-456 -567 22
-457 -568 39
-458 -569 13
-459 -570 50
-460 -571 37
-461 -572 14
-462 -573 26
-463 -574 49
-464 -575 23
-465 -576 44
-466 -577 2
-4...

output:

50
100 430 -943 -493 -604 431 -942 -492 -603 432 -941 -491 -602 433 -940 -490 -601 434 -939 -489 -600 435 -938 -488 -599 436 -937 -487 -598 437 -936 -486 -597 438 -935 -485 -596 439 -934 -484 -595 440 -933 -483 -594 441 -932 -482 -593 442 -931 -481 -592 443 -930 -480 -591 444 -929 -479 -590 445 -928...

result:

ok ok Sum L = 5000

Test #18:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

50
-142 0 48
-143 1 22
-144 2 45
-145 3 9
-146 4 36
-147 5 46
-148 6 26
-149 7 26
-150 8 9
-151 9 19
-152 10 22
-153 11 14
-154 12 8
-155 13 20
-156 14 41
-157 15 47
-158 16 22
-159 17 50
-160 18 3
-161 19 12
-162 20 15
-163 21 32
-164 22 46
-165 23 45
-166 24 3
-167 25 27
-168 26 33
-169 27 17
-170...

output:

50
100 488 -860 -191 49 489 -861 -190 48 490 -862 -189 47 491 -863 -188 46 492 -864 -187 45 493 -865 -186 44 494 -866 -185 43 495 -867 -184 42 496 -868 -183 41 497 -869 -182 40 498 -870 -181 39 499 -871 -180 38 500 -872 -179 37 501 -873 -178 36 502 -874 -177 35 503 -875 -176 34 504 -876 -175 33 505 ...

result:

ok ok Sum L = 5000

Test #19:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

12
1000 1000 50
1000 -1000 50
1000 999 50
999 1000 50
999 -1000 50
-999 1000 50
1000 -999 50
-999 -1000 50
-1000 1000 50
-1000 -1000 50
-1000 -999 50
-1000 999 50

output:

50
24 765 -1371 -1000 -1000 766 -1371 -999 -1000 765 -1370 -1000 -999 842 -967 999 -1000 843 -967 1000 -1000 843 -966 1000 -999 765 628 -1000 999 765 629 -1000 1000 766 629 -999 1000 843 1032 1000 999 842 1033 999 1000 843 1033 1000 1000
24 -196 -1169 -1000 -1000 -195 -1169 -999 -1000 -196 -1168 -10...

result:

ok ok Sum L = 1200

Test #20:

score: 0
Accepted
time: 0ms
memory: 3924kb

input:

4
1000 1000 50
1000 -1000 50
-1000 1000 50
-1000 -1000 50

output:

50
8 296 -3353 -1000 -1000 296 -1353 -1000 1000 371 142 1000 -1000 371 2142 1000 1000
8 -89 -2654 -1000 -1000 -89 -654 -1000 1000 -14 841 1000 -1000 -14 2841 1000 1000
8 -474 -1955 -1000 -1000 -474 45 -1000 1000 -399 1540 1000 -1000 -399 3540 1000 1000
8 -859 -1256 -1000 -1000 -859 744 -1000 1000 -7...

result:

ok ok Sum L = 400

Extra Test:

score: 0
Extra Test Passed